Számítástudomány elemei gyakorlat
11. feladatsor (2002. nov. 21.)

1. Keressük meg az alábbi egyenletek megoldásait (ha léteznek) az egész számok körében!
   1. $27x+63y=50$
   2. $71x-50y=1$

2. 1. Adjuk meg a $17x\equiv3+5x\pmod{51}$ kongruencia összes megoldását $\mod{51}\;$!

   2. Milyen megoldásai vannak a $21x\equiv14\pmod{35}$ kongruenciának $\mod{35}$?
      (Vizsga, 2001. jún.)

3. Oldjuk meg az alábbi kongruenciákat!
   1. $5x\equiv61\pmod{444}$
   2. $202x\equiv157\pmod{203}$

4. Igazoljuk az Euler-Fermat-tétel segítségével, hogy $4^{24}-3^{24}$ osztható 35-tel!
   (Vizsga, 1999. jún.)

5. Határozzuk meg $303^{404}$ utolsó két számjegyét! (Pótzh, 1999. máj.)

6. Milyen maradékot ad 75-tel osztva $88^{89^{98}}$? (Pótzh, 2001. dec.)

7. Igazoljuk, hogy ha $n>0$ páratlan egész szám, akkor $2^{n!}-1$ osztható $n$-nel.

8. Keressünk olyan $n$ természetes számokat, amelyekre $\varphi(n)=2,4,14$!

9. Legyen $p_1$ és $p_2$ két prímszám úgy, hogy $p_1>p_2$. Adjuk meg az összes olyan $p_1,p_2$ számpárt, amelyekre $p_2^{p_1}\equiv2\pmod{p_1}$ teljesül! (Vizsga, 2000. máj.)

10. Bizonyítsuk be, hogy tetszőleges $p$ prímre $(a+b)^p\equiv a^p+b^p\pmod{p}\;$!

11. Bizonyítsuk az ismert 9-cel való oszthatósági szabályt! (Útmutatás: legyen $b$ 10-es számrendszerbeli felírása $a_na_{n-1}...a_0$, ekkor igazoljuk, hogy $b\equiv a_0+a_1+...+a_n\pmod9$ teljesül.)