Tdn for beginners..
Sia $p>3$ un primo. Definiamo $n=\frac{2^{2p}-1}{3}$. Mostrare che $n|2^n-2$ 
Risposte
Vediamo dapprima che $n in ZZ$:
$2^(2p)-1 \equiv 0 mod 3$
$2^(2p) \equiv 1 mod 3$
Che è sempre verificato, visto che $phi(3)=2$
Ora procedendo analogamente ho che:
$2^n \equiv 2 mod n$
e funziona se $gcd(n,2)=1$, ma vediamolo in dettaglio:
$gcd((2^(2p)-1)/3,2)={(2 rightarrow 2|n),(1 ):}$
ma da qui se $2|n$
$(2^(2p)-1)/3 \equiv 0 mod 2$
porta a:
$-1 \equiv 0 mod 2$
quindi
$gcd((2^(2p)-1)/3,2)=1$
ed allora vale il piccolo teorema di Fermat e si ottiene l'asserto.
$2^(2p)-1 \equiv 0 mod 3$
$2^(2p) \equiv 1 mod 3$
Che è sempre verificato, visto che $phi(3)=2$
Ora procedendo analogamente ho che:
$2^n \equiv 2 mod n$
e funziona se $gcd(n,2)=1$, ma vediamolo in dettaglio:
$gcd((2^(2p)-1)/3,2)={(2 rightarrow 2|n),(1 ):}$
ma da qui se $2|n$
$(2^(2p)-1)/3 \equiv 0 mod 2$
porta a:
$-1 \equiv 0 mod 2$
quindi
$gcd((2^(2p)-1)/3,2)=1$
ed allora vale il piccolo teorema di Fermat e si ottiene l'asserto.
"Lord K":
Vediamo dapprima che $n in ZZ$:
$2^(2p)-1 \equiv 0 mod 3$
$2^(2p) \equiv 1 mod 3$
Che è sempre verificato, visto che $phi(3)=2$
Ora procedendo analogamente ho che:
$2^n \equiv 2 mod n$
e funziona se $gcd(n,2)=1$, ma vediamolo in dettaglio:
$gcd((2^(2p)-1)/3,2)={(2 rightarrow 2|n),(1 ):}$
ma da qui se $2|n$
$(2^(2p)-1)/3 \equiv 0 mod 2$
porta a:
$-1 \equiv 0 mod 2$
quindi
$gcd((2^(2p)-1)/3,2)=1$
ed allora vale il piccolo teorema di Fermat e si ottiene l'asserto.
mi sa che tu hai un po di confusione con la tdn visto che con tutto il tuo post mostri solo che $n \equiv 1 mod 2 \in \mathbb{N}$ e il che mi pare abbastanza scontato; e soprattutto ermat non è applicabile come fai te..
mmm... ci ho provato per vedere se ricordavo qualcosa di teoria dei numeri ma pare di no...
l'unica cosa che ho fatto è raccogliere un 2, notare che n è dispari ed espandere la sommatoria per vedere che la tesi è uguale a dire:
$2^4*2^(4^2)...*2^(4^(p-1))=1 mod n$
volendo si può notare che ogni fattore della sommatoria è uguale al precedente elevato alla quarta... ma non mi è sevito per studiarne il comportamento modulo n...
ora non credo che ci sia da studiare $\phi(n)$ e vedere qualcosa come $\phi(n)|(n-1)$ (anche perchè non saprei fare) visto che una ricerca su internet mi dice che questo equivarrebbe a trovare un numero detto di carmichael in maniera banale...
aiutino?
l'unica cosa che ho fatto è raccogliere un 2, notare che n è dispari ed espandere la sommatoria per vedere che la tesi è uguale a dire:
$2^4*2^(4^2)...*2^(4^(p-1))=1 mod n$
volendo si può notare che ogni fattore della sommatoria è uguale al precedente elevato alla quarta... ma non mi è sevito per studiarne il comportamento modulo n...
ora non credo che ci sia da studiare $\phi(n)$ e vedere qualcosa come $\phi(n)|(n-1)$ (anche perchè non saprei fare) visto che una ricerca su internet mi dice che questo equivarrebbe a trovare un numero detto di carmichael in maniera banale...
aiutino?
"Thomas":
l'unica cosa che ho fatto è raccogliere un 2, notare che n è dispari ed espandere la sommatoria per vedere che la tesi è uguale a dire:
$2^4*2^(4^2)...*2^(4^(p-1))=1 mod n$
[...]
aiutino?
Tesi: se sai che $n\ equiv 1 \mod 2$ e vuoi mostrare che $n| 2(2^{n-1}-1)$ allora devi mostrare soltanto che $2^{n-1} \equiv 1 \mod2$.
La tua tesi è equivalente infatti poichè $2^4*2^(4^2)...*2^(4^(p-1))= 2^{(\sum_{i=1}^{p-1}{4^i})}=2^{\frac{4^p-4}{3}}=2^{n-1}$.
(Pensavo che l'esercizio sarebbe stato bruciato in pochi minuti quando l'ho postato, invece..)
aiutino? ripassare quale sia il significato di phi, di ordine, e il teorema di euler-fermat..
mi sa che tu hai un po di confusione con la tdn visto che con tutto il tuo post mostri solo che $n \equiv 1 mod 2 \in \mathbb{N}$ e il che mi pare abbastanza scontato; e soprattutto ermat non è applicabile come fai te..
Dimmi cosa non funziona... per piacere
"bboypa":
[quote="Thomas"]l'unica cosa che ho fatto è raccogliere un 2, notare che n è dispari ed espandere la sommatoria per vedere che la tesi è uguale a dire:
$2^4*2^(4^2)...*2^(4^(p-1))=1 mod n$
[...]
aiutino?
Tesi: se sai che $n\ equiv 1 \mod 2$ e vuoi mostrare che $n| 2(2^{n-1}-1)$ allora devi mostrare soltanto che $2^{n-1} \equiv 1 \mod2$.
La tua tesi è equivalente infatti poichè $2^4*2^(4^2)...*2^(4^(p-1))= 2^{(\sum_{i=1}^{p-1}{4^i})}=2^{\frac{4^p-4}{3}}=2^{n-1}$.
(Pensavo che l'esercizio sarebbe stato bruciato in pochi minuti quando l'ho postato, invece..)
aiutino? ripassare quale sia il significato di phi, di ordine, e il teorema di euler-fermat..[/quote]
credo che intendessi $\mod n$ in quella congruenza, vero?
cmq che la tesi fosse equivalente lo sapevo l'ho riscritta io in quel modo
... il fatto che tu mi abbia fatto i passaggi all'incontrario credo sia un segnale che è meglio se riguardo il problema come l'hai scritto, giusto?...devi avere pazienza ho perso la poca familiarità con questi concetti che avevo al liceo... grazie per l'aiutino vedo se riesco a tirare fuori qualcosa
!
Ci sono! almeno credo...
Allora a noi farebbe mooolto comodo sapere ord$_a(b)$, dove $a$ indica l'elemento e $b$ il gruppo in cui lavoriamo, ovvero il gruppo moltiplicativo $Z_b^{star}$. Naturalmente $a=2$ e $b=(4^p-1)/3$.
Ma quale è questo ordine? proviamo a vedere cosa fa $2^(2p) modn$, anzi puntiamo al grosso e supponiamo che faccia $1$, ovvero che lui meno uno sia divisibile per $n$. Verifichiamo:
$\frac{2^(2p)-1}{2^(2p)-1)/3=3$
a questo punto sappiamo che l'ordine divide $2p$. Basta vedere a questo punto che $2p$ divide $n-1$ per verificare la tesi, il che equivale a dire raccogliendo un $4$ che $(4^(p-1)-1)/3$ è divisibile per $p$. Il numeratore è divisibile per $p$ causa fermat e causa $p>2$. Inoltre l'intera frazione rimane divisibile per $p$ causa $p>3$. E così si è concluso!
Allora a noi farebbe mooolto comodo sapere ord$_a(b)$, dove $a$ indica l'elemento e $b$ il gruppo in cui lavoriamo, ovvero il gruppo moltiplicativo $Z_b^{star}$. Naturalmente $a=2$ e $b=(4^p-1)/3$.
Ma quale è questo ordine? proviamo a vedere cosa fa $2^(2p) modn$, anzi puntiamo al grosso e supponiamo che faccia $1$, ovvero che lui meno uno sia divisibile per $n$. Verifichiamo:
$\frac{2^(2p)-1}{2^(2p)-1)/3=3$
a questo punto sappiamo che l'ordine divide $2p$. Basta vedere a questo punto che $2p$ divide $n-1$ per verificare la tesi, il che equivale a dire raccogliendo un $4$ che $(4^(p-1)-1)/3$ è divisibile per $p$. Il numeratore è divisibile per $p$ causa fermat e causa $p>2$. Inoltre l'intera frazione rimane divisibile per $p$ causa $p>3$. E così si è concluso!
mi lascia un pò perplesso che bboypa aveva suggerito la funzione $\phi$ di Eulero della quale però nella mia presunta soluzione non vi è traccia...
Partiamo dal riscrivere n:
$n=\frac{2^{2p}-1}{3}=\frac{4^p-1}{3}$, che è sempre intero poichè $4 \equiv 1 (mod 3)$
Riscriviamo anche $2^n-2$:
$ 2^n-2=2^{\frac{4^p-1}{3}}-2=2\cdot2^{\frac{(4^p-4)}{3}}-2$
La tesi dice che $\frac{4^p-1}{3}|2\cdot2^{\frac{(4^p-4)}{3}}-2$
Dimostriamo una cosa migliore, cioè che $(4^p-1)|2\cdot2^{\frac{(4^p-4)}{3}}-2$
Poichè $MCD(4^p-1;2)=1$ allora dobbiamo dimostrare che $(4^p-1)|2^{\frac{(4^p-4)}{3}}-1$
Ma $2^{\frac{(4^p-4)}{3}}-1=4^{\frac{(2^{2p-1}-2)}{3}}-1$
Quindi $(4^p-1)|4^{\frac{(2^{2p-1}-2)}{3}}-1$, cioè $4^{\frac{(2^{2p-1}-2)}{3}} \equiv 1 (mod 4^p-1)$.
Ma anche $4^p \equiv 1 (mod 3)$.
Quindi $ord_{4^p-1} 4 | MCD(p;\frac{(2^{2p-1}-2)}{3})$.
Poichè l'MCD deve dividere p, ne deduciamo che $ord_{4^p-1} 4|p$, cioè che è pari o a 1 o a p.
Se l'ordine è pari a 1, allora avremo $3 \equiv 0 (mod 4^p-1)$ e quindi che p=1, che è assurdo.
Se l'ordine è pari a p, avremo che $p|\frac{(2^{2p-1}-2)}{3}$, che significa che dobbiamo dimostrare che $p|(2^{2p-1}-2)$ poichè p>3. ma
$2^{2p-1}-2 \equiv 2^{2(p-1)+1}-2 \equiv 2-2 \equiv 0 (mod p)$ e quindi è dimostrato.
$n=\frac{2^{2p}-1}{3}=\frac{4^p-1}{3}$, che è sempre intero poichè $4 \equiv 1 (mod 3)$
Riscriviamo anche $2^n-2$:
$ 2^n-2=2^{\frac{4^p-1}{3}}-2=2\cdot2^{\frac{(4^p-4)}{3}}-2$
La tesi dice che $\frac{4^p-1}{3}|2\cdot2^{\frac{(4^p-4)}{3}}-2$
Dimostriamo una cosa migliore, cioè che $(4^p-1)|2\cdot2^{\frac{(4^p-4)}{3}}-2$
Poichè $MCD(4^p-1;2)=1$ allora dobbiamo dimostrare che $(4^p-1)|2^{\frac{(4^p-4)}{3}}-1$
Ma $2^{\frac{(4^p-4)}{3}}-1=4^{\frac{(2^{2p-1}-2)}{3}}-1$
Quindi $(4^p-1)|4^{\frac{(2^{2p-1}-2)}{3}}-1$, cioè $4^{\frac{(2^{2p-1}-2)}{3}} \equiv 1 (mod 4^p-1)$.
Ma anche $4^p \equiv 1 (mod 3)$.
Quindi $ord_{4^p-1} 4 | MCD(p;\frac{(2^{2p-1}-2)}{3})$.
Poichè l'MCD deve dividere p, ne deduciamo che $ord_{4^p-1} 4|p$, cioè che è pari o a 1 o a p.
Se l'ordine è pari a 1, allora avremo $3 \equiv 0 (mod 4^p-1)$ e quindi che p=1, che è assurdo.
Se l'ordine è pari a p, avremo che $p|\frac{(2^{2p-1}-2)}{3}$, che significa che dobbiamo dimostrare che $p|(2^{2p-1}-2)$ poichè p>3. ma
$2^{2p-1}-2 \equiv 2^{2(p-1)+1}-2 \equiv 2-2 \equiv 0 (mod p)$ e quindi è dimostrato.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo