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 $.
Successioni e coprimalità II: the revenge
-
- Moderatore
- Messaggi: 1053
- Iscritto il: 01 gen 1970, 01:00
- Località: Pescara
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.
$ 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.