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?




Fogaras Daniel 2003-04-25