Congruenza

Numeri interi, divisibilità, primalità, ed equazioni a valori interi.

Congruenza

Messaggioda Salvador » 25/08/2017, 22:45

Dimostrare che esistono infiniti interi positivi composti $n$ tali che $2^{n-1} \equiv 1 \pmod{n}$.
Salvador
 
Messaggi: 265
Iscritto il: 26/11/2016, 11:55

Re: Congruenza

Messaggioda Rho33 » 26/08/2017, 20:27

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!
Rho33
 
Messaggi: 489
Iscritto il: 16/09/2014, 11:14

Re: Congruenza

Messaggioda lucioboss99 » 27/08/2017, 16:16

A occhio direi che è una semplice conseguenza del teorema di eulero.
lucioboss99
 
Messaggi: 18
Iscritto il: 07/09/2016, 12:59

Re: Congruenza

Messaggioda Fenu » 19/09/2017, 17:37

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}$.
Fenu
 
Messaggi: 1
Iscritto il: 19/09/2017, 17:22


Torna a Teoria dei Numeri

Chi c’è in linea

Visitano il forum: Gizeta e 1 ospite