$n\mid a-b$ sse $n\mid ab-1$

[jordan]

Trovare tutti gli interi positivi $n\ge 2$ tali che \[ n\mid a-b \text{ se e solo se } n\mid ab-1 \]
per ogni $a,b$ interi tali che $\text{gcd}(a,n)=\text{gcd}(b,n)=1$.

[Simo_the_wolf]

Hola! C'è un piccolo problema mi pare... bisogna assumere che $(a,n)=1$ altrimenti non funziona solo per $n=1$, prendendo $a=2n$ e $b=n$.

[jordan]

Ovviamente hai ragione, mea culpa
Ciao Simo!

[aetwaf]

$ab-1=kn$ quindi $a=\frac {kn+1} b$ quindi $n\mid \frac {kn+1-b^2} b$ quindi $b^2=1\pmod n$ quindi $b=1\pmod n$ o $b=-1\pmod n$.
Ma se la proprietà deve valere per ogni $n$ allora dovremo avere $-1=0\pmod n$ o $1=0\pmod n$ da cui $n=1$ o $n=-1$.

[jordan]

Sbaglio o $n=2$ funziona? Trova l'errore

[aetwaf]

Sbaglio o $n=2$ funziona? Trova l'errore

Hai ragione dovevo dire che se $b\equiv1\pmod n$ allora $a\equiv1\pmod n$, se $b\equiv-1\pmod n$ allora $a\equiv-1\pmod n$.
Inoltre se la proprietà vale $\forall a,b$ allora dovremo avere $1+1=2\equiv0 \pmod n$ quindi $n=-1$ o $n=1$ o $n=2$ o $n=-2$.

[jordan]

Come prima cosa, chiede di trovare solo gli interi $n\ge 2$ (è ovvio che se $n$ funziona allora lo sarà anche $-n$); secondo, ancora non hai trovato l'errore, visto che stai ancora saltando qualche soluzione..

[Gottinger95]

Allora, \(n \mid ab-1 \ \ \Rightarrow n \mid a-b\) significa che se due numeri sono inversi \(\pmod{n}\) e coprimi con \(n\) allora sono congrui \(\pmod{n}\). D'altronde due numeri \(a,b\) sono inversi se e solo se esistono \(h,k \in \mathbb{Z}\) tali che \( ha+kb = 1\). Se \(a=b = m\) allora
\(1 = | (h+k)m| = |h+k| \cdot |m|\)
da cui \(m = \pm 1\). Visto che i numeri coprimi con \(n\) possono essere solo \(1, n-1\), deve valere \(\varphi(n) \le 2\), da cui \(n=2,3,4\), che effettivamente verificano anche l'altra freccia.

[darkcrystal]

Per favore, qualcuno provi $n=24$...

[jordan]

...i suoi divisori, e che non ne esistono altri!

[Gottinger95]

Due pranzi di natale sono troppi; abiuro ciò che ho detto e riposto una soluzione.

Sia \(d\) un divisore di \(n\). Se \(n \mid a-b \ \ \Leftrightarrow n \mid ab-1\) allora \(d \mid n \mid a-b \ \ \Leftrightarrow d \mid n \mid ab-1\), dunque vale anche per \(d\). Sia \(p\) un primo che divide \(n\). Per ogni \(a\) minore di \(p\) deve valere \(a^2 \equiv 1 \pmod{p}\); perciò c'è un solo residuo quadratico, 1. Visto che i residui quadratici sono \( (p-1)/2\), deve essere \(p \le 3\).
D'altronde \(9 \nmid n\), perchè \( 2^2 \equiv 4 \pmod{9}\); e \(16 \nmid n\), perchè \(3^2 \equiv 9 \pmod{16}\).
Dunque \(n \mid 24\), ed effettivamente tutti i suoi divisori verificano (per TCR basta verificare \(8\) e \(3\) ).

[jordan]

Finalmente