Doti naturāli skaitļi \(a\), \(b\) un \(m\); \(\mbox{LKD}(a,b)=1\). Pierādiet, ka aritmētiskajā progresijā \(ak+b\), (\(k=0,1,2,\ldots\)) ir bezgalīgi daudz locekļu, kas ir savstarpēji pirmskaitļi ar skaitli \(m\).
Apzīmēsim ar \(A\) visu tādu skaitļa \(m\) pirmreizinātāju reizinājumu, kuri ir arī skaitļa \(a\) dalītāji.
Apzīmēsim ar \(B\) visu tādu skaitļa \(m\) pirmreizinātāju reizinājumu, kuri ir arī skaitļa \(b\) dalītāji.
Apzīmēsim ar \(C\) visu tādu skaitḷa \(m\) pirmreizinātāju reizinājumu, kuri nav ne \(a\) ne \(b\) dalītāji.
Tad \((A, B)=(A, C)=(C, B)=1\).
Pierādīsim, ka \((aAC+b, m)=1\). Pieņemsim pretējo, ka eksistē pirmskaitlis \(p\), kurš dala \(aAC+b\) un \(m\). Ja \(p \mid m\), tad \(p\) dala \(A,B\) vai \(C\).
Ja \(A\) dalās ar \(p\), tad no tā, ka \(aAC+b\) dalās ar \(p\), seko, ka arī \(b\) dalās ar \(p\). No tā, ka \(b\) un \(m\) dalās ar \(p\), seko, ka \(B\) dalās ar \(p\). Iegūta pretruna ar to, ka \((A, B)=1\). Līdzīgi nonākam pie pretrunas arī gadījumos, kad \(B\) vai \(C\) dalās ar \(p\).
Tātad \((a A C+b, m)=1\); bet tad arī
\[(a(A C+t m)+b, m)=(a A C+b, m)=1.\]
Ņemot aritmētiskajā progresijā \(ak+b\) un \(k = AC + tm\), mēs iegūsim bezgalīgi daudz locekļus, kuri ir savstarpēji pirmskaitļi ar \(m\).