Number Theory & Divisibility

Medium2–3 hrsModular ArithmeticGCDFermatLast DigitRemainders

Overview

Number theory puzzles test recognition of modular patterns. Powers of integers repeat modulo any fixed number — the cycle is always short. Fermat's Little Theorem is the elegant reason: for prime p, a^(p-1) ≡ 1. This converts 'what is 2^{1000} mod 101?' into a trivial calculation. The Euclidean GCD algorithm is also directly tested — practice it until it's automatic.

How to Recognize

→'What is the last digit of 7^{100}?'
→'Find the remainder when dividing X by Y'
→GCD/LCM problems
→Powers of numbers follow repeating cycles mod any fixed base

Step-by-Step Approach

1.Last digit = mod 10. Find the cycle: compute a^1, a^2, ... mod 10 until repeat.
2.Fermat's Little Theorem: a^(p−1) ≡ 1 (mod p) for prime p, gcd(a,p)=1
3.GCD: Euclidean algorithm — gcd(a,b) = gcd(b, a mod b)
4.For composite moduli: Euler's theorem: a^φ(n) ≡ 1 (mod n)

Key Formulas

01Fermat:

a^{p-1} \equiv 1 \pmod{p}

(prime

p

\gcd(a,p)=1

)

02Euler:

a^{\phi(n)} \equiv 1 \pmod{n}

(

\gcd(a,n)=1

)

03GCD Euclidean:

\gcd(a,b) = \gcd(b,\, a \bmod b)

04LCM:

\text{lcm}(a,b) = ab/\gcd(a,b)

Worked Examples

0Quick Example

Last digit of 7^100: cycle is 7→9→3→1 (length 4). 100 mod 4 = 0 → 4th element = 1. Answer: 1.

Problem

What is the last digit of 3^{47}?

Solution

Compute 3^n mod 10: 3^1=3, 3^2=9, 3^3=27→7, 3^4=81→1, 3^5=243→3. Cycle repeats with period 4: (3, 9, 7, 1).

47 mod 4 = 3 (since 47 = 11×4 + 3).

3rd element of cycle (3, 9, 7, 1) = 7.

Last digit of 3^{47} = 7.

Answer

7. Cycle for powers of 3 mod 10 has length 4: (3,9,7,1). Since $47 \equiv 3 \pmod 4$ , last digit = 7.

Common Mistakes

!
Using Fermat when the modulus is not prime. Fermat requires prime p. For composite n, use Euler's theorem with φ(n).
!
Off-by-one in cycle position when exponent mod period = 0. n mod 4 = 0 means use the FOURTH position of the cycle, not the first.
!
LCM formula: lcm(a,b) = ab/gcd(a,b). Never compute LCM by brute force for large numbers.

Practice Problems

Click "Show Answer" to reveal

What is the last digit of 9^{999}?

Hint: Cycle for 9 mod 10: 9, 1, 9, 1, ... (period 2).

What is 7^{52} mod 13?

Hint: 13 is prime. Fermat: 7^12 ≡ 1 (mod 13). Write 52 = 4×12 + 4.

What is the sum of all integers from 1 to 100 that are NOT multiples of 3 or 5?

Hint: Total sum minus multiples of 3 minus multiples of 5 plus multiples of 15.

Back to Study Plan

Classic Probability Brainteasers Fast Multiplication & Squaring