Congruenza
Congruenza
Dimostrare che esistono infiniti interi positivi composti $n$ tali che $2^{n-1} \equiv 1 \pmod{n}$.
Re: Congruenza
Non metto la soluzione perché per ben due volte consecutive ho letto male/ risolto un testo diverso dall'originale (stento a crederci anche io...), quindi quello che è uscito fuori sono due varianti del problema, entrambe a mio parere interessanti per gli approcci/lemmi.
1) Trovare tutti gli $n \geq 1$ tali che $2^{n-1} \equiv -1 \pmod n$
2) Dimostrare che esistono infiniti $n$ composti tali che $$ 1+2+...+2^{\text{ord}_n(2)-1} \equiv 0 \pmod n$$
P.S. Appena ho tempo, proverò anche l'originale, promesso!
1) Trovare tutti gli $n \geq 1$ tali che $2^{n-1} \equiv -1 \pmod n$
2) Dimostrare che esistono infiniti $n$ composti tali che $$ 1+2+...+2^{\text{ord}_n(2)-1} \equiv 0 \pmod n$$
P.S. Appena ho tempo, proverò anche l'originale, promesso!
-
lucioboss99
- Messaggi: 21
- Iscritto il: 07/09/2016, 12:59
Re: Congruenza
A occhio direi che è una semplice conseguenza del teorema di eulero.
Re: Congruenza
Facile vedere che $n= 2^{2^k} + 1$ funziona.
Lavoriamo in $\mathbb{Z}/n\mathbb{Z}$, allora $$2^{2^k}=-1$$
Eleviamo entrambe le parti per $2^{2^k - k}$.
$$2^{2^k \cdot 2^{2^k - k}}=1$$
E quindi
$$2^{2^{k + 2^k - k}} = 2^{2^{2^k}}=1$$
Ma il termine al centro non e' altro che $2^{n-1}$.
Lavoriamo in $\mathbb{Z}/n\mathbb{Z}$, allora $$2^{2^k}=-1$$
Eleviamo entrambe le parti per $2^{2^k - k}$.
$$2^{2^k \cdot 2^{2^k - k}}=1$$
E quindi
$$2^{2^{k + 2^k - k}} = 2^{2^{2^k}}=1$$
Ma il termine al centro non e' altro che $2^{n-1}$.