Aplūkojam visus naturālos skaitļus no \(1\) līdz
\(2\,000\,000\) ieskaitot. Izvēlēsimies
no tiem kaut kādus \(1\,000\,001\) skaitļus.
(A) Pierādīt, ka starp izvēlētajiem skaitļiem
noteikti atradīsies divi tādi, kas ir savstarpēji
pirmskaitļi.
(B) Vai to noteikti var apgalvot, ja tiek izvēlēti
\(1\,000\,000\) skaitļi?
Vispirms pierādīsim, ka divi viens otram sekojoši naturāli skaitli ir savstarpēji pirmskaitļi. Tiešām \((n,(n+1))=(n,(n+1)-n)=(n, 1)=1\).
Sadalīsim visus dotos skaitļus pāros:
\[(1,2),(3,4), \ldots,(1999999,2000000).\]
Tādu pāru ir \(1000000\). Mums ir jāizvēlas \(1000001\) skaitlis; tātad vismaz divi skaiţ̦i būs no viena pāra - tie būs savstarpēji pirmskaitļi. \(1000000\) skaitļus izvēlēties var: jāņem visi pāra skaitļi; jebkuri divi no tiem nav savstarpēji pirmskaitli, jo tie abi dalās ar \(2\).