Problem B. 3961. (December 2006)

B. 3961. Let a and b denote positive integers, such that aⁿ+n divides bⁿ+n for all positive integers n. Prove that a=b.

(5 pont)

Deadline expired on January 15, 2007.

Sorry, the solution is available only in Hungarian. Google translation

Megoldás: Mivel végtelen sok prímszám van, létezik végtelen sok olyan $p_1,p_2,\ldots$ prímszám is, melyek nem osztói sem a-nak, sem b-nek. Ha tehát valamely i-re p=p_i, akkor a kis Fermat tétel értelmében a^p-1 és b^p-1 is 1 maradékot ad p-vel osztva, sőt bármilyen pozitív k egész számra igaz, hogy $a^{k(p-1)}\equiv b^{k(p-1)}\equiv 1\pmod{p}$ . Ennélfogva minden

$n\in N=\{(p-1)+1, 2(p-1)+1,\ldots,p(p-1)+1\}$

esetén igaz, hogy $a^n\equiv a\pmod{p}$ és $b^n\equiv b\pmod{p}$ .

N elemei közül bármely kettő különbsége k(p-1) alakba írható valamely 1 és p-1 közé eső k egész számmal, tehát nem lehet p-vel osztható. Ezért az N halmaz p eleme mind különböző maradékot ad p-vel osztva, vagyis ezen maradékok között az összes lehetséges maradék előfordul, amely p-vel való osztásnál keletkezhet. Van tehát egy olyan n $\in$ N, amelyre n p-vel osztva ugyanolyan maradékot ad, mint -a, vagyis a+n osztható p-vel. Mivel aⁿ-a is osztható p-vel, kapjuk hogy aⁿ+n, és így bⁿ+n, következésképpen b+n is osztható p-vel. Ebből viszont már következik, hogy b-a is osztható p-vel.

A b-a szám tehát osztható a végtelen sok $p_1,p_2,\ldots$ prímszám mindegyikével, következésképpen csak 0 lehet, vagyis valóban a=b.

Statistics:

16 students sent a solution.

5 points: Bodor Bertalan, Szűcs Gergely.

2 points: 4 students.

0 point: 10 students.

Problems in Mathematics of KöMaL, December 2006

16 students sent a solution.
5 points:	Bodor Bertalan, Szűcs Gergely.
2 points:	4 students.
0 point:	10 students.

Already signed up?
New to KöMaL?