liczby względnie pierwsze

gelo · Post autor: **gelo** » 19 gru 2010, 11:19

Pokazać, że w ciągu \({2 ^{n}-3}\) istnieje nieskończenie wiele liczb, z których każde dwie są względnie pierwsze.

gpl1260 · Post autor: **gpl1260** » 19 gru 2010, 20:57

Jak na zadanie z IMO (1971 r., zad.3.), nie jest trudne.

gelo · Post autor: **gelo** » 19 gru 2010, 21:20

Możesz zapodać linka do rozwiązania??

gpl1260 · Post autor: **gpl1260** » 19 gru 2010, 21:34

Naturalnym pomysłem jest indukcja. Dwie takie liczby względnie pierwsze znajdziemy. Jeśli mamy takich liczb k, to trzeba znaleźć (k+1)-szą, która będzie względnie pierwsza z iloczynem tych k liczb które już mamy. W tym celu znajdujemy liczbę postaci 2^p-1 podzielną przez ten iloczyn, i jako poszukiwaną (k+1)-szą liczbę bierzemy 2^p-3 (jest dobra, bo dwie kolejne liczby nieparzyste są względnie pierwsze).

gelo pisze:Możesz zapodać linka do rozwiązania??

http://www.cs.cornell.edu/~asdas/imo/imo/imo71.html