Maths WorkshopMaths problems with full solutions
Exercise 624Number theory › Divisibility and gcdM1Added 4 Nov 2026

13 divides 2⁷⁰ + 3⁷⁰

#Fermat's little theorem#modular exponentiation

Statement

Prove that 1313 divides 270+3702^{70}+3^{70}.

Hint

By Fermat's little theorem a12≡1(mod13)a^{12}\equiv1\pmod{13}. Reduce the exponents. Also 33=27≡1(mod13)3^3=27\equiv1\pmod{13}.

Show solutionHide solution

Solution

Powers of 22. 70=5⋅12+1070=5\cdot12+10, so 270≡210=1024(mod13)2^{70}\equiv2^{10}=1024\pmod{13}. Since 1024=13⋅78+101024=13\cdot78+10, 270≡102^{70}\equiv10.

Powers of 33. 33=27≡1(mod13)3^3=27\equiv1\pmod{13}, and 70=3⋅23+170=3\cdot23+1, so 370≡31=33^{70}\equiv3^1=3.

Sum. 270+370≡10+3=13≡0(mod13)2^{70}+3^{70}\equiv10+3=13\equiv0\pmod{13}.

Remark. Another approach: 270+3702^{70}+3^{70} is divisible by 1313 because 32≡−4=−22(mod13)3^2\equiv-4=-2^2\pmod{13}, hence 370=(32)35≡(−4)35=−2703^{70}=(3^2)^{35}\equiv(-4)^{35}=-2^{70}.

Lesson. Reduce the base and the exponent: use Fermat's theorem (or the actual order) to shrink exponents modulo p−1p-1 (or modulo the order).