Little math problem(s) May 2021

[Albert Chan]

(05-03-2021 10:19 PM)PeterP Wrote:  Always love your posts Albert, as I learn so much. Can you help me grasp the a^5 = a(mod30) identity easily?

a^5 - a
= (a^4-1)*a
= (a-1)*a*(a+1) * (a²+1)
= (a-1)*a*(a+1) * ((a+2)*(a+3) - 5*(a+1))
= (a-1)*a*(a+1)*(a+2)*(a+3)       -       5*(a-1)*a*(a+1)²

Both terms are divisible by 30, so does (a^5 -a)

Or, we can use 5 is prime → a^5 ≡ a (mod 5)       -- Fermat's little theorem

(a^5 - a) has factor 2, 3 and 5, thus divisible by 2*3*5 = 30

Brute force also very easy (only 3 points needed), for f(a) = a^5 - a

f(0) = 0
f(1) = 1 - 1 = 0
f(2) = 32 - 2 = 30 = 6*5

Because f(a) is odd function, we have these for free: f(-1) = -0, f(-2) = -6*5

a^5 - a ≡ 0 (mod2, mod3 and mod5)
a^5 - a ≡ 0 (mod 30)