Mutassa meg, hogy az 5^20 + 2^30 összetett szám. ?

Alakítsuk egy picit:

(5^20-1) + (2^30+1)

Sejtés: az 1. rész osztható 5^2+1=26-tal (és így 13-mal), a 2. osztható 2^6+1=65-tel (és így 13-mal)

1. (25^10-1)*(25^10+1)

(25^10-1)=(25^5-1)*(25^5+1)

(25^5+1)=(25+1)*...

2. (2^6)^5+1 = (64+1)*...

[link]

Persze úgy könnyebb rájönni, ha a 13-mal oszthatóság megmutatása a feladat! :-)

Bocsi, elq..., helyesen:

1. 25^10-1 = (25^5-1)*(25^5+1)

(25^5+1)=(25+1)*...

5^20+2^30=(5^2)^10+(2^3)^10.

Itt egy nevezetes azonosság segít: (a-b)|a^{2n}+b^{2n}. (Ezt egyszerű belátni.)

(a-b)|a^{2n}+b^{2n} nem igaz,

pl. a=5, b=2, n=1;

(5-2)=3 nem osztója 5^2 + 2^2 = 25 + 4 = 29-nek

Amik igazak:

a-b | a^n - b^n

a+b | a^{2n} - b^{2n}

a+b | a^{2n+1} + b^{2n+1}

Most az utóbbi használható:

5^20 + 2^30 = (5^4)^5 + (2^6)^5 = 625^5 + 64^5

625+64=689 | 625^5 + 64^5 azaz:

689 | 625^5 + 64^5