Bevezetés a számításelméletbe II.
10. gyakorlat 2003. április 18.
 
 
Euler-Fermat-tétel, csoportok

 

1. Mely $n$ számokra teljesül, hogy $2 \varphi(n) = n$ ?
2. Milyen maradékot ad 99-el osztva
   1. $1996^{668}$
   2. $1996^{659}$ ?
3. Mi az utolsó két számjegye (tízes számrendszerben) az alábbi számnak:
   1. $1997^{\textstyle 2001^{\textstyle 2005}}$
   2. HF $1997^{\textstyle 2003^{\textstyle 2005}}$ ?
4. Bizonyítsuk be, hogy $n^7-n$ osztható 42-vel, tetszőleges $n$ egész esetén!
5. Félcsoportot, csoportot illetve Abel-csoportot alkot-e az alább megadott $H$ halmaz a $*$ művelettel?
   1. $H$ az egész számok halmaza és az $a,b \in H$ számokra $a * b := a+b+1$, ahol a szokásos összeadás szerepel;
   2. $H := \{1,2, \dots, 6\}$. Továbbá $a * b:=ab \pmod{7}$;
   3. $H := \{1,2, \dots, 7\}$. Továbbá $a * b:=ab \pmod{8}$;
   4. $H$ az egész számok halmaza és az $a,b \in H$ számokra $a * b := a^b$;
   5. $H$ azon $f$ függvények halmaza, melyek $f(x)=cx+d$ alakúak, ahol $c \neq 0$. A $*$ művelet pedig a függvények egymás után való alkalmazása (amit analízisből $f \circ g$-vel jelöltetek.)
   6. HF $H$ a valós számok halmaza és $a * b := a+b +ab$.
   7. HF $H$ a 2002 pozitív osztóinak halmaza, és az $a,b \in H$ számokra $a *b:= d(a,b)$, azaz $a$ és $b$ legnagyobb közös osztója.
   8. HF $H$ azon modulo $m$ maradékosztályok halmaza, amelyek $m$-mel relatív prímek. Továbbá $a * b:=ab \pmod{m}$;
   9. HF $H$ egy halmaz hatványhalmaza (összes részhalmazinak halmaza), és az $a,b \in H$ részhalmazokkal $a * b := (a \setminus b) \cup (b \setminus a)$ (amit szimmetrikus differenciának is neveznek);
6. HF Melyik az a legkisebb pozitív szám, amely osztóinak száma 9?
7. HF Milyen maradékot ad 103-mal osztva $205^{206^{207}}$ ?
8. HF Oldjuk meg az alábbi kongruenciákat!
   1. $x^{12001} \equiv 5 \pmod{13}$;
   2. $x^{11999} \equiv 5 \pmod{13}$
9. HF Mutassuk meg, hogy ha $a^{12}+b^{12}+c^{12}$ osztható 7-tel, akkor $7^{12}$-nel is!
10. HF Mely $m>1$ egészre és $p$ prímre teljesül, hogy $\varphi(pm) = \varphi(m)$ ?
11. HF Tudjuk, hogy az $a$ egész számra $a^{100} \equiv 5 \pmod{31}$ és $a^{101} \equiv 19 \pmod{31}$. Milyen maradékot ad 31-gyel való osztáskor az $a$ szám?