Bevezetés a számításelméletbe II.
8. gyakorlat 2003 április 4.
 
 
Legnagyobb közös osztó, prímek

 

1. Ha $b$ osztója $a$-nak, akkor mik lehetnek az értékei a $d(a,a+b)$ és a $d(2a, a-b)$ legnagyobb közös osztóknak?
2. 1. Az euklideszi algoritmus segítségével számítsuk ki az 504 és a 396 legnagyobb közös osztóját!
   2. Fejezzük is ki a legnagyobb közös osztót $q\cdot 504 + r \cdot 396$ alakban, ahol $q$ és $r$ egészek!
   3. Mennyi 504 és 396 legkisebb közös többszöröse?
3. Bizonyítsuk be, hogy az
   $$\frac{a^3+2a}{a^4+3a^2+1}$$
   tört semmilyen $a$ egész esetén sem egyszerűsíthető!
4. Bizonyítsuk be, hogy négy egymást követő pozitív egész szám között mindig van olyan, amelyik a másik három mindegyikéhez (külön-külön) relatív prím.
5. Mutassuk meg, hogy az $1,2,\ldots,kn$ számok közül bárhogyan választunk ki $n$ darabot, lesz köztük két olyan, amelyek legnagyobb közös osztója nem nagyobb $k$-nál!
6. Igazoljuk, hogy tetszőleges $n_1, n_2, \ldots, n_k$ egészekhez található olyan $r>1$ szám, amelyik minden $n_i$-vel relatív prím!
7. HF A $b$ és $c$ számok relatív prímek és különbségük osztható 5-tel. Igazoljuk, hogy $b+c$ és $2b+7c$ is relatív prímek.
8. HF Határozzuk meg a $d(9k+4,2k-1)$ legnagyobb közös osztót, majd ennek segítségével igazoljuk, hogy $9k+4$ és $2k-1$ legkisebb közös többszöröse legalább $k^2$, ha $k\ge 3$.
9. HF Legyenek $k$ és $n$ olyan pozitív egészek, amelyekre $k<n$. Mi a legnagyobb közös osztója az $n!+1$ és az $(n+1)!+k$ számoknak?