Hardcore talteori problem

Man skal med andre ord undersøge, om ligningen

n(n+1)/2 ≡ 13 (mod 100)

har positive løsninger.

Hvis der skal gælde

1+2+...+n = n·(n+1)/2 ≡ 13 (mod 100)

vil n·(n+1)/2 -13 være deleligt med 100, og der vil da findes et helt tal m, så at

n·(n+1)/2 -13 = m·100 , eller

n·(n+1) -26 = 200·m , eller

n² + n -6 = 200·m + 20, dvs.

(n-2)·(n+3) = 20·(10m+1) .

Højresiden skal være delelig med 20 = 2·2·5 og med 10m+1 . Venstresiden skal derfor også være delelig med 5. Da 5 er et primtal, må 5 derfor enten gå op i (n+3) eller i (n-2) . men da forskellen mellem (n+3) og (n-2) selv er 5, må 5 derfor gå op både i (n+3) og i (n-2). Venstresiden er derfor delelig med 5² = 25, så højresiden må også være delelig med 5² . Det betyder, at 5 må gå op i 10m+1. Men dette er umuligt, da 5 går op i 10m og derfor ikke kan gå op i 10m+1 . Der findes derfor ikke noget helt tal m, så at
n·(n+1)/2) -13 = m·100 , og derfor vil tallet n·(n+1)/2 ikke ende med cifrene 13 for noget n.