non trovo l'errore

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
wotzu
Messaggi: 52
Iscritto il: 16 dic 2015, 21:33

non trovo l'errore

Messaggio da wotzu »

ho trovato questo problemino che dovrebbe essere semplice e sicuramente lo è.
lo scrivo esattamente come viene enunciato:
if none of the numbers $a,a+d,\cdots,a+(n-1)d$ is divisible by $n$, then $d$ and $n$ are coprime.
I numeri sono $n$, tuttavia nessuno di essi è congruo a zero$\pmod{n}$ quindi si devono distribuire in $n-1$ classi di resto, quindi ci sono due numeri $a+kd,a+jd$ ,con $j\ne k$, tali che $a+kd\equiv a+jd \pmod{n}$.
semplificando si ottiene $(k-j)d\equiv 0 \pmod{n}$ ma dato che $|k-j|\le n-1$, $d$ deve per forza contenere qualche divisore di $n$.
dove sbaglio?
Gi8
Messaggi: 42
Iscritto il: 17 ago 2012, 12:04

Messaggio da Gi8 »

Direi che è falsa: prendi $a=1$, $d=2$, $n=2$. La sequenza è $1, 3$. Nessuno di questi numeri è divisibile per $n$, ma $(d,n)=(2,2)=2$.
Rispondi