Oszthatóság és szabályok

A 36-tal való oszthatóság feltétele, hogy a szám osztható legyen 4-gyel és 9-cel (mivel ezek relatív prímek). A 4-gyel való oszthatóság miatt az utolsó két számjegyéből álló számnak oszthatónak kell lennie 4-gyel, így a $2b$ szám osztható 4-gyel. Ebből $b$ lehetséges értékei: 0, 4, 8. A 9-cel való oszthatóság miatt a számjegyek összegének, azaz $10 + a + b$-nek oszthatónak kell lennie 9-cel.

Ha $b=0$, akkor $10+a$ osztható 9-cel, így $a=8$.
Ha $b=4$, akkor $14+a$ osztható 9-cel, így $a=4$.
Ha $b=8$, akkor $18+a$ osztható 9-cel, így $a=0$ vagy $a=9$.
A megoldások: 53820, 53424, 53028 és 53928.

Legyen a kétjegyű szám $10a+b$, ahol $a$ és $b$ számjegyek ($a \neq 0$). A számjegyeinek felcserélésével kapott szám $10b+a$. A két szám összege: $$(10a+b) + (10b+a) = 11a + 11b = 11(a+b)$$ Mivel $a+b$ egész szám, a kifejezés mindig osztható 11-gyel.

Szabály: Egy 4-es számrendszerben felírt szám pontosan akkor osztható 3-mal, ha a számjegyeinek összege osztható 3-mal (hasonlóan a 10-es számrendszer 9-cel való oszthatóságához).

Bizonyítás: Írjuk fel a számot helyiértékes alakban: $N = c_k 4^k + \dots + c_1 4^1 + c_0 4^0$. Mivel $4 \equiv 1 \pmod 3$, ezért $4^n \equiv 1^n = 1 \pmod 3$ minden $n$-re. Ezt behelyettesítve kapjuk, hogy $N \equiv c_k + \dots + c_1 + c_0 \pmod 3$, ami éppen a számjegyek összege.

Egy 8-as számrendszerben felírt szám helyiértékes alakja $N = c_k 8^k + \dots + c_1 8^1 + c_0$. Vizsgáljuk az alap 9-cel vett maradékát: $8 \equiv -1 \pmod 9$. Ebből következik, hogy $8^n \equiv (-1)^n \pmod 9$.

Így $N \equiv c_0 - c_1 + c_2 - c_3 + \dots \pmod 9$. Tehát a számnak pontosan akkor osztható 9-cel, ha a hátulról képzett váltakozó előjelű számjegyösszege osztható 9-cel. Ez az analógiája a 10-es számrendszerbeli 11-gyel való oszthatóságnak.

Alakítsuk szorzattá a kifejezést: $$n^3 - n = n(n^2 - 1) = (n - 1)n(n + 1)$$ Látható, hogy a kifejezés három egymást követő egész szám szorzata. Három egymást követő egész szám között biztosan van legalább egy páros (így a szorzat osztható 2-vel), és pontosan egy osztható 3-mal. Mivel a 2 és a 3 relatív prímek, a szorzatuk osztható lesz $2 \cdot 3 = 6$-tal.

A hatványozás azonosságait használva alakítsuk át a kifejezést: $$3^{2n} - 1 = (3^2)^n - 1 = 9^n - 1$$ Alkalmazzuk az $a^n - b^n = (a-b)(a^{n-1} + a^{n-2}b + \dots + b^{n-1})$ algebrai azonosságot $a=9$ és $b=1$ választással. $$9^n - 1^n = (9 - 1)(9^{n-1} + \dots + 1) = 8 \cdot K$$ Mivel a kifejezés egyik tényezője 8, a szorzat minden $n \ge 1$ esetén osztható 8-cal.

Legyen a négy egymást követő szám $x$, $x+1$, $x+2$ és $x+3$. A kifejezésünk: $$K = x(x+1)(x+2)(x+3) + 1$$ Szorozzuk össze a külső és belső párokat: $$K = [x(x+3)] \cdot [(x+1)(x+2)] + 1 = (x^2+3x)(x^2+3x+2) + 1$$ Vezessünk be egy új változót: $y = x^2+3x$. Ezzel felírva: $$K = y(y+2) + 1 = y^2 + 2y + 1 = (y+1)^2$$ Visszahelyettesítve $y$-t kapjuk, hogy a kifejezés értéke $(x^2+3x+1)^2$. Mivel $x^2+3x = x(x+3)$, ami egy páros szám (egyik tényezője biztosan páros), ezért $x^2+3x+1$ mindenképpen páratlan szám. Tehát valóban egy páratlan szám négyzetét kaptuk.

Emeljük ki a közös tényezőt, az $5^n$-t az összegből: $$5^n \cdot 5^2 + 2 \cdot 5^n \cdot 5^1 + 5^n = 5^n (25 + 10 + 1) = 5^n \cdot 36$$ A kifejezés felírható egy egész szám és a 36 szorzataként, így a feladat állítását igazoltuk.

Ha $n+1$ osztható 3-mal, akkor létezik olyan $k$ egész szám, hogy $n+1 = 3k$, amiből $n = 3k-1$. Helyettesítsük be ezt az eredeti kifejezésbe: $$(3k-1)^2 + 5(3k-1) + 8 = 9k^2 - 6k + 1 + 15k - 5 + 8 = 9k^2 + 9k + 4$$ Ezt írhatjuk a következő alakba is: $$3(3k^2 + 3k + 1) + 1$$ Ez a kifejezés 3-mal osztva 1 maradékot ad (és nem 2-t). Bár az állítás, hogy "2 maradékot ad" nem teljesült (tehát a kijelentésként adott képlet maradéka 1), a lényeg, hogy nem osztható 3-mal maradéktalanul.

Tudjuk, hogy ha $n$ páratlan szám, akkor $a^n + b^n$ felbontható úgy, hogy tartalmazza az $(a+b)$ tényezőt. Alakítsuk át az eredeti kifejezést, hogy páratlan kitevőt kapjunk: $$2^{70} + 3^{70} = (2^2)^{35} + (3^2)^{35} = 4^{35} + 9^{35}$$ Itt $a=4$, $b=9$, és a kitevő 35, ami páratlan. Az azonosság alapján ez az összeg osztható lesz $a+b = 4+9 = 13$-mal.

Írjuk fel a számot helyiértékes alakban: $$N = 100000a + 10000b + 1000c + 100a + 10b + c$$ Emeljük ki a megfelelő helyiértékeket: $$N = 1000(100a + 10b + c) + 1(100a + 10b + c)$$ $$N = 1001 \cdot (100a + 10b + c)$$ Vizsgáljuk meg az 1001 prímtényezős felbontását: $1001 = 7 \cdot 11 \cdot 13$. Mivel a szám mindig felírható az 1001 és az $abc$ háromjegyű szám szorzataként, így mindhárom vizsgált prímmel osztható lesz.

A 16-os számrendszer alapjára igaz, hogy $16 \equiv 1 \pmod{15}$. Ennek alapján a 16-os számrendszerbeli 15-tel való oszthatóság szabálya tökéletesen megegyezik a 10-es számrendszerbeli 9-cel (vagy 3-mal) való oszthatóság szabályával: az osztási maradék megegyezik a számjegyek összegének osztási maradékával.

A számjegyek a 16-os rendszerben: $A=10$, az 5 az 5, $B=11$. Összegük: $10 + 5 + 11 = 26$. A 26-ot elosztva 15-tel a maradék 11. Így az eredeti szám 15-tel való osztási maradéka is 11.

Bontsuk fel a kifejezést: $p^2 - 1 = (p-1)(p+1)$. Mivel $p > 3$ prím, így $p$ biztosan páratlan. Ebből következik, hogy $p-1$ és $p+1$ két egymást követő páros szám. Két egymást követő páros szám közül az egyik mindig osztható 4-gyel, a másik 2-vel, így a szorzatuk osztható 8-cal.

Továbbá, mivel $p$ prím és $p>3$, $p$ nem osztható 3-mal. Három egymást követő egész szám ($p-1, p, p+1$) közül pontosan egy osztható 3-mal. Mivel ez nem a $p$, ezért vagy a $p-1$, vagy a $p+1$ biztosan többszöröse a 3-nak.

A szorzat tehát osztható 8-cal és 3-mal is. Mivel (8, 3) = 1, a szorzat osztható 24-gyel.

Alakítsuk szorzattá a kifejezést úgy, hogy egy teljes négyzetté egészítjük ki, majd levonjuk a hozzáadott tagot (két négyzet különbsége): $$n^4 + 4 = n^4 + 4n^2 + 4 - 4n^2 = (n^2 + 2)^2 - (2n)^2$$ Ezután alkalmazzuk az $a^2 - b^2 = (a-b)(a+b)$ azonosságot: $$(n^2 - 2n + 2)(n^2 + 2n + 2) = ((n-1)^2 + 1)((n+1)^2 + 1)$$ Ahhoz, hogy egy szorzat prímszám legyen a pozitív egészek körében, a kisebbik tényezőnek 1-nek kell lennie. Mivel $(n+1)^2 + 1 > 1$ minden pozitív $n$-re, ezért csak az $(n-1)^2 + 1 = 1$ feltétel jöhet szóba. Ebből $(n-1)^2 = 0$, tehát $n=1$. Ekkor az érték $1^4+4 = 5$, ami valóban prím.

Alakítsuk szorzattá a kifejezést: $$x^5 y - x y^5 = xy(x^4 - y^4) = xy(x^2 - y^2)(x^2 + y^2) = xy(x - y)(x + y)(x^2 + y^2)$$ A 30-cal való oszthatósághoz a 2, 3 és 5-tel való oszthatóságot kell vizsgálni.
2-vel: Ha $x$ vagy $y$ páros, a szorzat páros. Ha mindkettő páratlan, akkor $x-y$ páros. Így mindig osztható 2-vel.
3-mal: Ha valamelyik osztható 3-mal, a szorzat is. Ha egyik sem, akkor mindkettő maradéka 1 vagy 2. Ha a maradékok egyeznek, $x-y$ osztható 3-mal. Ha különböznek, $x+y$ osztható 3-mal. Így a 3-mal való oszthatóság is teljesül.
5-tel: Alkalmazzuk a Kis Fermat-tételt: $x^5 \equiv x \pmod 5$ minden $x$-re. Így $x^5 y - x y^5 \equiv xy - xy = 0 \pmod 5$.
Mivel a 2, 3 és az 5 relatív prímek, a kifejezés mindig osztható $2 \cdot 3 \cdot 5 = 30$-cal.

Vizsgáljuk meg a számok 3-as maradékait. Egy szám 3-as maradéka 0, 1 vagy 2 lehet.
Ha $p=3$, akkor $p+10 = 13$ és $p+14 = 17$. Mindkettő prímszám, így ez egy érvényes megoldás.
Ha $p > 3$, akkor $p$ nem lehet osztható 3-mal, vagyis $p \equiv 1 \pmod 3$ vagy $p \equiv 2 \pmod 3$.
Eset 1: Ha $p \equiv 1 \pmod 3$, akkor $p+14 \equiv 1+14 = 15 \equiv 0 \pmod 3$. Ekkor $p+14$ osztható 3-mal (és mivel $p>3$, nagyobb 3-nál), így összetett szám.
Eset 2: Ha $p \equiv 2 \pmod 3$, akkor $p+10 \equiv 2+10 = 12 \equiv 0 \pmod 3$. Ekkor a $p+10$ lesz osztható 3-mal, így összetett szám.
Tehát az egyetlen megoldás a $p=3$.

Rendezzük az egyenletet egy oldalra: $xy - x - y = 0$. Adjunk mindkét oldalhoz 1-et, hogy a bal oldal szorzattá alakítható legyen: $$xy - x - y + 1 = 1$$ Ebből kiemelésekkel kapjuk: $$x(y - 1) - 1(y - 1) = 1 \implies (x - 1)(y - 1) = 1$$ Mivel $x$ és $y$ egészek, két egész szám szorzata csak úgy lehet 1, ha mindkettő 1, vagy mindkettő -1.
1. eset: $x-1 = 1$ és $y-1 = 1$, amiből $x=2$ és $y=2$.
2. eset: $x-1 = -1$ és $y-1 = -1$, amiből $x=0$ és $y=0$.
Megoldáshalmaz: $(0, 0)$ és $(2, 2)$.

Bontsuk fel a számlálót úgy, hogy ki tudjunk emelni egy $(n+2)$-es tényezőt: $$n^2 + 5n + 12 = n^2 + 2n + 3n + 6 + 6 = n(n+2) + 3(n+2) + 6 = (n+3)(n+2) + 6$$ Helyettesítsük vissza a törtbe: $$\frac{(n+3)(n+2) + 6}{n+2} = n + 3 + \frac{6}{n+2}$$ Mivel $n+3$ mindig egész szám, a tört értéke akkor lesz egész, ha $\frac{6}{n+2}$ is egész. Ez akkor teljesül, ha $n+2$ osztója a 6-nak. A 6 egész osztói: $\pm 1, \pm 2, \pm 3, \pm 6$. Ebből az $n$ lehetséges értékei a sorrendet tartva: $-1, -3, 0, -4, 1, -5, 4, -8$.

A feladat értelmében a számrendszer alapja $k$. A $144_k$ szám értékét polinom alakban felírva az alábbit kapjuk: $$N = 1 \cdot k^2 + 4 \cdot k^1 + 4 \cdot k^0 = k^2 + 4k + 4$$ Ez a kifejezés egy nevezetes azonosság, teljes négyzetté alakítható: $$k^2 + 4k + 4 = (k+2)^2$$ Mivel $k$ alapú számrendszerről beszélünk, a legmagasabb használt számjegy a 4-es, ezért a feltétel $k>4$ garantálja, hogy a felírás érvényes. A kapott érték pedig, mivel $k$ egész, valóban mindig egy egész szám $(k+2)$ négyzete.

Az összeg 1998 tagból áll. Alkosson párokat az összeg elejéről és végéről haladva: $$ (1^{1999} + 1998^{1999}) + (2^{1999} + 1997^{1999}) + \dots + (999^{1999} + 1000^{1999}) $$ Általánosan felírva a párokat: $k^{1999} + (1999-k)^{1999}$. Mivel a kitevő (1999) páratlan szám, alkalmazható az $a^n + b^n = (a+b)(a^{n-1} - \dots + b^{n-1})$ azonosság. Ez azt jelenti, hogy a kifejezés mindig osztható lesz az alapok összegével: $$ k + (1999-k) = 1999 $$ Tehát minden egyes pár összege osztható 1999-cel. Mivel az összegben pontosan 999 pár található kimaradó tag nélkül, a teljes összeg is maradéktalanul osztható 1999-cel.