Neka [tex]\{a_n\}_1^{100}[/tex] aritmetička progresija sa 100 elemenata. [tex]a_1=5[/tex], [tex]a_2=8[/tex] i tako dalje. [tex]\{b_n\}_1^{100}[/tex] takođe ima 100 elemenata, ali je [tex]b_1=3[/tex], [tex]b_2=7[/tex] i tako dalje. Pronađi koliko zajedničkih elemenata [tex]\{a_n\}[/tex] i [tex]\{b_n\}[/tex] imaju.
Rešenje:
Znamo da za bilo koje [tex]k \in [0,99][/tex]: [tex]a_{k+1}=3k+5[/tex] za bilo koje [tex]l[/tex] u istom intervalu, [tex]b_{l+1}=4l+3[/tex]. Tražimo događaje [tex]a_{k+1}=b_{l+1}[/tex] za bilo koje k,l za dati interval. To je jednako
[tex]3k+5=4l+3[/tex]
[tex]4l=3k+2[/tex]
[tex]l=\frac{3k+2}{4}[/tex]. Sada imamo l kao funkciju od k. Za date vrednosti, [tex]l=\frac{3k+2}{4} \le \frac{3\cdot 99+2}{4}<75[/tex], pa nećemo ići van ograničenja za l. Po definiciji, l je ceo broj, i trebalo bi da bude [tex]\frac{3k+2}{4}[/tex]. Pa tragamo za vrednostima od k između 0 i 99, za koje je [tex]\frac{3k+2}{4}[/tex] ceo broj. Odatle sledeće mora biti tačno: [tex]3k+2 \equiv 0 (mod 4)[/tex]
[tex]3k+2-4k \equiv 0 (mod 4)[/tex]
[tex]2-k \equiv 0 (mod 4)[/tex]
[tex]k \equiv 2 (mod 4)[/tex].
Ovi brojevi su u nizu [tex]2,6,10,...,98[/tex] i ima ih ukupno 25.