Successioni e coprimalità II: the revenge

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Simo_the_wolf
Moderatore
Messaggi: 1036
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Successioni e coprimalità II: the revenge

Messaggio da Simo_the_wolf » 13 mag 2005, 14:17

Dato un intero positivo k, definiamo $ a_1 = k+1 $ e $ a_{n+1} = a_n^2-ka_n+k $ per $ n > 1 $.
Dimostrare che se $ m \neq n $ allora $ MCD(a_n,a_m)=1 $.

Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll » 13 mag 2005, 20:01

Allora, si può provare innanzitutto che tutti i termini sono congrui a $ 1 $ modulo $ k $. Lo si fa agilmente per induzione poichè
$ a_1\equiv k+1\equiv 1 $ $ (\mod k) $
se funziona $ a_n $
$ a_{n+1}\equiv 1^2-k+k\equiv 1 $ $ (\mod k) $
Quindi per induzione abbiamo la tesi.
Possiamo ora quindi affermare che, comunque preso $ d $, divisore di $ k $ diverso da $ 1 $, esso non divide nessun termine della progressione.

Ora dimostriamo che comunque presi due termini $ a_m, a_n $, tali che, per simmetria $ m>n $ si avrà che:
$ a_m\equiv k $ $ (\mod a_n) $
chiamato $ m-n=j $ ragioniamo per induzione su $ j $
per $ j=1 $ avremo
$ a_{n+1}=a_n(a_n-k)+k $ quindi vero
se funzia per $ j $
$ a_{n+j}\equiv k $
$ a_{n+j+1}\equiv k^2-k*k+k\equiv k $
induzione finita

Ora avremo quindi che, detto $ g=gcd(a_m,a_n) $, sempre con $ m>n $ avremo
$ g|a_n $
$ g|a_m=i*a_n+k $ per qualche $ i\in \mathbb{Z} $
quindi
$ g|i*a_n+k-i*a_n=k $ (regole della divisibilità)
ma, per quanto affermato precedentemente $ g $ non può essere un divisore di $ k $ diverso da $ 1 $, quindi si ha la tesi.

Avatar utente
Pixel
Messaggi: 79
Iscritto il: 23 feb 2005, 16:16
Località: Trento

Messaggio da Pixel » 14 mag 2005, 17:33

Equivalentemente si poteva dimostrare per induzione che per ogni m:

$ (a_{m},a_{n})=(a_{n},k) $ fissato n
quindi dimostrare che per ogni n:
$ (a_{n},k)=1 $ e avere la tesi.
P. Andrea

Rispondi