veelvoud van 2001

Opgave - IrMO 2001 dag 2 vraag 3

Vind het kleinste natuurlijke getal $m$ waarvoor $55^n+m32^n$ een veelvoud is van 2001 voor een zekere oneven $n$.

Oplossing

"Modulo Modulo Modulo" - Gauss

$2001 = 3 * 23 * 29$, we zullen dus modulo $3,23,29$ nemen van het LL.

$55 \equiv 1 \pmod3$
$\longrightarrow 55^n \equiv 1^n \pmod 3$
$\longrightarrow 55^n \equiv 1 \pmod 3$

$32 \equiv 2 \pmod 3$
$32 \equiv -1 \pmod 3$
$32^n \equiv -1^n \pmod 3$
$n$ is oneven, dus
$32^n \equiv -1 \pmod 3$

$55^n + m*32^n \equiv 0 \pmod 3$
$1 + m(-1) \equiv 0 \pmod 3$
$1(1-m) \equiv 0 \pmod 3$
$\longrightarrow m \equiv 1 \pmod 3$ (1)

$55 \equiv 9 \pmod 23$
$55^n \equiv 9^n \pmod {23}$
$32 \equiv 9 \pmod {23}$
$32^n \equiv 9^n \pmod {23}$
$\longrightarrow 55^n + m * 32^n \equiv 0 \pmod {23}$
$9^n + m * 9^n \equiv 0 \pmod {23}$
$9^n(1+m) \equiv 0 \pmod {23}$
$\longrightarrow m \equiv -1 \pmod {23}$ (2)

$55 \equiv -3 \pmod {29}$
$\longrightarrow 55^n \equiv -3^n \pmod {29}$ (n oneven, dus negatief)
$32 \equiv 3 \pmod {29}$
$\longrightarrow 32^n \equiv 3^n \pmod {29}$

$\longrightarrow -3^n + m * 3^n \equiv 0 \pmod {29}$
$\longrightarrow 3^n(1-m) \equiv 0 \pmod {29}$
$\longrightarrow m \equiv 1 \pmod {29}$ (3)

Uit (1),(2),(3) kunnen we het $m$ op 3 manieren schrijven:
$m = 3a+1 = 23b-1 = 29c+1$
$3a+1 = 29c+1$
$3a = 29c$
$c \equiv 0 \pmod 3$
Herschrijf beide als $87x$
Dus $87x +1 = 23b-1$
$87x+2 = 23b$
$87x \equiv -2 \pmod {23}$
en $87 \equiv 18 \pmod {23}$
$x \equiv x \pmod {23}$ want we willen $x$ zo klein mogelijk.
$18x \equiv -2 \mod {23}$
Als we nu de veelvouden van $23$ even uitschrijven, vinden we $23,46,69,92$ etc
$92 \equiv 2 \pmod {18}$
$18x +2 = 92$

$x = 5$
We hebben nu dat $m = 87 * 5 = 435$