grootste gemene deler
Opgave - JBaMO 1999 vraag 2
Voor ieder natuurlijk getal $n$ definiëren we $A_n=2^{3n}+3^{6n+2}+5^{6n+2}$. Vind de grootste gemene deler van $A_0,A_1,...,A_{1999}$.
voorbeeld: ggd(2,3,6)=1
- login om te reageren
Olympia
Nederlandstalig olympiadeproject
Zoeken
Random generator
Niveau
Wie is online
Er zijn momenteel 0 gebruikers en 0 gasten online.
Oplossing
Merk op dat $A_0 = 35$ en $A_1 = 397194$ snel te berekenen waarden zijn. Nu zal dus $\gcd\left(A_0,A_1,A_2,\cdots,A_{1999}\right) \leq \gcd\left(A_0,A_1\right) = \gcd\left(35,397194\right) = 7$. We moeten dus enkel zien of alle $A_i$ deelbaar zijn door 7. Als dat niet het geval is, is 1 de grootste gemene deler. Anders is dat 7 natuurlijk.
Maareuhm... $$2^{3n} + 3^{6n+2} + 5^{6n+2} = 8^n + 9\cdot 729^n + 25\cdot 15625^n \equiv 1 + 2\cdot 1 + 4\cdot 1 \equiv 0\mod{7}$$