Zadanie

Narzędzia
Obiekty: Ciągi liczbowe
Słowa kluczowe
Kategoria: Teoria liczb

Klub 44M - zadania XI 2010»Zadanie 610

o zadaniu...

Zadanie pochodzi z artykułu Klub 44M - zadania XI 2010
Publikacja w Delcie: listopad 2010
Publikacja elektroniczna: 20 grudnia 2010
Zadanie 610 zaproponował pan Michał Kieza z Warszawy.

Ciąg $\text{[math]}$ jest określony rekurencyjnie: $\text{[math]}$ , $\text{[math]}$ ,

display-math

Dowieść, że żaden wyraz tego ciągu nie ma dzielnika dodatniego postaci $\text{[math]}$

Rozwiązanie

Określamy parę ciągów $\text{[math]}$ $\text{[math]}$ wzorami: $\text{[math]}$

display-math

(1)

Wówczas $\text{[math]}$ oraz

display-math

co pokazuje, że $\text{[math]}$ jest ciągiem danym w zadaniu. Ze wzorów (1) dostajemy równość

display-math

a ponieważ $\text{[math]}$ wynika stąd, że $\text{[math]}$

Określamy parę ciągów $\text{[math]}$ $\text{[math]}$ wzorami: $\text{[math]}$

display-math

(2)

Wówczas $\text{[math]}$ oraz

$pict$

co pokazuje, że $\text{[math]}$ jest ciągiem danym w zadaniu. Ze wzorów (1) dostajemy równość

display-math

a ponieważ $\text{[math]}$ wynika stąd, że $\text{[math]}$

Ustalmy $\text{[math]}$ Widać, że $\text{[math]}$ jest liczbą nieparzystą. Niech $\text{[math]}$ będzie jej dowolnym dzielnikiem pierwszym. Dostajemy zależność

display-math

Po podniesieniu do potęgi $\text{[math]}$ (i skorzystaniu z małego twierdzenia Fermata: $\text{[math]}$ ),

display-math

(3)

Za chwilę wykażemy, że

display-math

(4)

Równość (mod $\text{[math]}$ ) prawych stron (2) i (3) oznacza, że

display-math

Dla $\text{[math]}$ parzystego warunek (4) mówi, że $\text{[math]}$ lub $\text{[math]}$ dla pewnego $\text{[math]}$ ; zatem $\text{[math]}$ lub $\text{[math]}$ Każdy dzielnik pierwszy liczby $\text{[math]}$ ma więc taką postać. Dowolny dzielnik dodatni (jako iloczyn pewnej liczby dzielników pierwszych) wtedy też jest tej postaci.

Dla $\text{[math]}$ nieparzystego warunek (4) implikuje $\text{[math]}$ lub $\text{[math]}$ czyli $\text{[math]}$ lub $\text{[math]}$ I znów, dowolny iloczyn takich liczb też jest liczbą tej postaci. W obu przypadkach liczby postaci $\text{[math]}$ nie mogą być dzielnikami liczby $\text{[math]}$

Pozostaje udowodnić wzór (3). Przyjmijmy (dla ustalonego $\text{[math]}$ ) oznaczenia:

$pict$

Iloczyn $\text{[math]}$ liczy $\text{[math]}$ czynników. Łączymy je z czynnikami iloczynu $\text{[math]}$ w pary o sumie $\text{[math]}$ (czyli $\text{[math]}$ ). Otrzymujemy związek $\text{[math]}$ (mod $\text{[math]}$ ). Stąd

$pict$

Wystarczy teraz podzielić przez czynnik $\text{[math]}$ (względnie pierwszy z $\text{[math]}$ ), by uzyskać wzór (3) i zakończyć rozwiązanie.