142. Congruenza modulo n

[mat94]

Trovare tutti gli interi positivi n tali che $ 2^{n-1}\equiv-1\pmod{n} $.

[Troleito br00tal]

Bozza sgrammaticata, la sistemo domattina.

Testo nascosto:

Sia $p$ il primo tale che $p|n$ e $b$ sia il più grande intero tale che $2^b|p-1$, in modo che $b$ sia il minimo possibile.

Sia ora $2^{n-1} \equiv -1$ (mod $p$), quindi $v_2(n-1)<v_2(ord_2(p) \le v_2(p-1)$, che è chiaramente assurdo.

Testo nascosto:

[Troleito br00tal]

Ok.

Testo nascosto:

Supponiamo per assurdo che qualche $n$ soddisfi la tesi.

Sia $p$ il primo tale che $p|n$ e tale che $b$ sia minimo (oppure uno dei minimi).

Ma chi è $b$? $b$ è il più grande intero positivo tale che $2^b|p-1$.

Adesso, per TCR, abbiamo che $2^{n-1} \equiv -1$ (mod $n$) implica $2^{n-1} \equiv -1$ (mod $q$) per ogni $q$ primo tale che $q|n$.

Quindi, ponendo $q \rightarrow p$, allora $2^{n-1} \equiv -1$ (mod $p$):
-$ord_p(2)|(2n-2)$;
-$ord_p(2)$ non divide $(n-1)$.

Ergo, $v_2(ord_p(2))>v_2(n-1)$, inoltre $v_2(p-1) \ge v_2(ord_p(2))$, poiché $ord_p(2)|p-1$. A questo punto, concatenando le disuguaglianze ottengo un assurdo:
$b=v_2(p-1) \ge v_2(ord_p(2))>v_2(n-1)$

Perché? Poiché $b$ è il minimo, quindi $v_2(n-1) \ge b$, che contrasta con quanto detto sopra.

[mat94]

Giusto a te il testimone. Bel problema vero? A me è piaciuto

[Troleito br00tal]

Bello ma esistevano soluzioni meno truccose?

[mat94]

Non saprei anche io l'ho fatto così