delirii da matematici

[Piera]

nel mio libro c'è una dimostrazione del teorema che nessun numero naturale maggiore di 1 divide
2^n -1 , se volete ve la posto...

[carlo23]

nel mio libro c'è una dimostrazione del teorema che nessun numero naturale maggiore di 1 divide
2^n -1 , se volete ve la posto...

Fantastico, così questo enigma non ci tormenterà più!
Comunque il problema è che nessun numero $k$ maggiore di 1 divide $2^k-1$, ti sei espressa male.

[Piera]

non ho capito, k è un intero o no?

[carlo23]

non ho capito, k è un intero o no?

è intero, anche io mi sono espesso male.

Dai, posta la dimostrazione!

[Piera]

Se n è primo il piccolo teorema di Fermat dice che n divide
2^n – 2 e quindi non può dividere 2^n –1.
Resta il caso in cui n non è primo.
Si osservi che se il numero primo p divide 2^n – 1
(p > 2 poiché 2^n – 1 è dispari), allora n e p-1 non sono primi tra loro:
se lo fossero (adesso il libro sfrutta un risultato che credo abbia dimostrato in qualche teorema precedente), esisterebbero tre numeri interi non negativi r, s , t tali che
r * n + s * (p-1) = t * ( p- 1) +1 ovvero
2^ (r * n) * 2^(s * (p-1)) = 2^( t * ( p- 1)) * 2
con la contraddizione che il primo membro ha resto 1 modulo p
( 2^n =1 mod p, quindi 2^(n * r) =1 mod p , per l’ipotesi che p divide
2^n –1 e 2^(p-1) =1 mod p, quindi 2^(s *(p-1)) =1 mod p, per il
piccolo teorema di Fermat)
e il secondo membro ha resto 2 modulo p come si può
verificare in stretta analogia con quanto osservato per il primo membro.

Se ora si considera p quale minimo divisore primo di n allora p-1 e n sono primi tra loro.
Per quanto sopra p non può dividere 2^n –1 e neanche n lo può.

[carlo23]

Grazie, la leggero con calma, sarebbe solo stato meglio se l'avessi postata scrivendo le formule con MathML, comunque va bene lo stesso.

Sono contento che la dimostrazione sia stata postata solo adesso, infatti se fosse stata postata prima allora ubermensch non avrebbe postato quella cosa sulle stime asintotiche e io non avrei potuto formulare quella teoria dei generatori.

[carlo23]

Si può evitare di usare quella cosa dei tre numeri fruttando il seguente risultato:

Si definisce ordine di 2 modulo $n$ (di solito si scrive $o_n(2)$)il minimo intero $s>0$ tale che $2^s -= 1 mod n$.
Se per $b>0$ si ha $2^b -= 1 mod n$ allora $o_n(2)$ divide $b$.


Detto questo se abbiamo che $p$ divide $2^n-1$ allora $2^n -= 1 mod p$, e $o_p(2)$ divide $n$.
Per il piccolo teorema di Fermat sappiamo anche che $2^(p-1) -= 1 mod p$ e quindi $o_p(2)$ divide $p-1$.
Da ciò segue che $n$ e $p-1$ non sono primi tra loro: hanno il fattore $o_p(2)$ in comune.

Grazie ancora Piera, per curiosità da che libro hai preso la dimostrazione?

[Piera]

avendo internet explorer 5 non posso istallare MathML e quindi non ha senso che impari ad usarlo...

la dimostrazione è stata presa da un libro di esercizi e complementi di matematica generale, e la parte dedicata alla teoria dei numeri all'incirca sarà una trentina di pagine (per interderci non è un libro di teoria e sui numeri praticamente non c'è alcun risultato) , quindi, visto che mi sembra di aver capito che sei un esperto dell'argomento, non credo che ti possa interessare.
il libro comunque è questo:
vannucci-visani
esercizi e complementi di matematica generale 1

[Valerio Capraro]

Per amor di completezza... (sperando che sia giusta)

Lemma
Dati due interi positivi a e b, detto d il loro MCD, allora esistono tre interi nonnegativi r,s,t tali che

ra + sb = tb + d

dimostrazione

In base all’identità di Bezout esistono due interi l,m non entrambi nulli, tali che

la + mb = k

Se l>0 e m >= 0 allora la tesi si ha con r = l, s = m e t = 0: se invece l > 0 e m < 0, allora scriviamo m = s – t con s,t > 0 opportuni, da cui facilmente la tesi; se l = 0 e m > 0, si procede analogamente al primo caso. Infine, se l < 0 e m > 0, distinguiamo due casi:


1) b >1
sommando e sottraendo al primo membro dell’identità di Bezout l’espressione –lba, essa può essere riscritta nella forma

(l – lb)a + (la + m)b = k

Che ci riporta ad uno dei casi già studiati, a seconda del segno di la + m.

2) b = 1
l’identità di Bezout diviene la + m*1 = 1; da cui si può subito osservare che m > 1, perché altrimenti si avrebbe la = 0 con l ed a non nulli. Ora, addizionando e sottraendo l’espressione –lm nell’identità di Bezout, essa si riscrive nella forma

(l – lm)a + (l + 1)m = 1

che ci riporta al caso precedente con l – lm > 0 e l+1 < 0

[carlo23]

avendo internet explorer 5 non posso istallare MathML e quindi non ha senso che impari ad usarlo...

Capisco, ero interessato perchè ho visto che in pò di tuoi post dicevi tipo "nel mio libro..." e allora mi sono chiesto: non avra mica il LIBRO (nel senso di Erdos)?!

Ciao,ciao!