What is the remainder when we divide 390 + 590 by 34?

Rewrite the expression:

3^90 + 5^90 = (3^2)^45 + (5^2)^45 = 9^45 + 25^45.

• Key property: for odd n, a^n + b^n is divisible by a + b. A short justification: modulo (a + b) we have a ≡ -b, so a^n ≡ (-b)^n = -b^n when n is odd, hence a^n + b^n ≡ 0 (mod a + b).

• Apply with a = 9, b = 25 and n = 45 (odd): 9^45 + 25^45 is divisible by 9 + 25 = 34.

Therefore the remainder when dividing 3^90 + 5^90 by 34 is 0.