Bevezetés a számításelméletbe II.
9. gyakorlat 2002. április 11-12.
Csütörtök 10-12 IB-140 és péntek 8-10 IB-145
 
 
Maradékosztályok

 

1. Az $x \equiv 2 \pmod{3}$ és az $x\equiv 5 \pmod{6}$ állítások közül melyik következik a másikból?

2. Oldjuk meg a $2x\equiv 2 \pmod{12}$ és a $3x\equiv 5\pmod{7}$ kongruenciákat!

3. Igazoljuk, hogy
   1. $39^{14}-1$ osztható 5-tel;
   2. HF $5555^{2222}-2$ osztható 7-tel.

4. Mi a nagyobb $10^{10^{10}}$ vagy $(10^{10})^{10}$ ?

5. Mennyi az utolsó számjegye a $13^{15^{17}}$ számnak?

6. Milyen maradékot ad 103-mal osztva $205^{206^{207}}$ ? (Segítség egy egyszerű trükkel nagyon leegyszerűsíthető a feladat.)

7. Mely $m$ egészre és $p$ prímre teljesül, hogy $\varphi(pm) = \varphi(m)$ ?

8. Van-e megoldása az alábbi kongruenciának $m=9,10$ és 11 esetben?
   
   $$6x \equiv 4 \pmod{m}$$
   
   

9. Oldjuk meg az alábbi kongruenciákat:
   1. $14 x \equiv 8 \pmod{21}$ ,
   2. $102 x \equiv -48 \pmod{45}$ (ZH feladat)
   3. $4 x \equiv 20 \pmod{14}$ (ZH feladat)
   4. $3^{26}x\equiv 2 \pmod{29}$ ,
   5. HF $45 x \equiv 120 \pmod{96}$ ,
   6. HF $6 x +1 \equiv 10 \pmod{15}$ (ZH feladat)

10. Mutassuk meg, hogy ha $a^{12}+b^{12}+c^{12}$ osztható 7-tel, akkor $7^{12}$-nel is.

11. HF Mely $n$ számokra teljesül, hogy $2 \varphi(n) = n$ ?

12. HF Bizonyítsuk be, hogy $n^7-n$ osztható 42-vel, ha $n$ tetszőleges szám. (Vigyázat, $n$ nem feltétlenül relatív prím 42-vel.)

13. HF Igazoljuk, hogy $n^{p^p} -n$ osztható $p$-vel tetszőleges $p$ prím és $n$ egész szám esetén.

14. HF Milyen maradékot ad 99-cel osztva $1996^{659}$ ? (Vegyük észre, hogy ez a feladat kongruenciává alakítható, különben elég sokat kéne számolni.)