An expression such as 7¹⁰⁰ looks too large to calculate, but a remainder question never asks for the full number. It asks you to preserve only what matters modulo n. With congruences, Euclid's algorithm, Euler's totient and modular inverses, the arithmetic stays small from the first step to the last.
1. Congruences: the language
We write
a ≡ b (mod n)
when n divides a - b. Equivalently, a and b leave the same remainder when divided by n. For example, 23 ≡ 3 (mod 10) because 23 - 3 = 20 is divisible by 10.
Congruences respect addition, subtraction and multiplication. If a ≡ b (mod n) and c ≡ d (mod n), then
a + c ≡ b + d (mod n)
and
ac ≡ bd (mod n).
This gives the most useful working habit: reduce early and keep reducing. For example,
38 × 47 ≡ 8 × 7 = 56 ≡ 6 (mod 10).
There is no need to calculate 38 × 47 = 1786 first, although it gives the same final remainder. Modular arithmetic groups integers that share a remainder; Set theory and relations: closures, equivalence and partial orders explained connects this congruence relation to equivalence classes.
2. GCD by the Euclidean algorithm
The Euclidean algorithm uses
gcd(a, b) = gcd(b, a mod b)
repeatedly until the remainder becomes 0. The last non-zero remainder is the greatest common divisor.
Find gcd(1071, 462):
1071 = 2 × 462 + 147,
462 = 3 × 147 + 21,
147 = 7 × 21 + 0.
The last non-zero remainder is 21, so
gcd(1071, 462) = 21.
You can verify it in both directions. First, 21 divides 1071 because 21 × 51 = 1071, and it divides 462 because 21 × 22 = 462. Second, the Euclidean chain shows that any common divisor of 1071 and 462 must also divide 147 and then 21, so no common divisor larger than 21 is possible.
GCD is the gatekeeper for modular inverses and Euler's theorem. An inverse of a modulo n exists exactly when gcd(a, n) = 1.
3. Euler's totient function
Euler's totient φ(n) counts the integers from 1 through n that are coprime to n. If p is prime, every positive integer below p is coprime to it, so φ(p) = p - 1.
For a number with distinct prime divisors p, the product formula is
φ(n) = n ∏(1 - 1/p).
For n = 36, the distinct prime divisors are 2 and 3:
φ(36) = 36(1 - 1/2)(1 - 1/3)
= 36 × 1/2 × 2/3
= 12.
A second check uses 36 = 4 × 9 and gcd(4, 9) = 1. Totient is multiplicative for coprime factors, so
φ(36) = φ(4)φ(9) = 2 × 6 = 12.
For n = 10, the prime divisors are 2 and 5.
φ(10) = 10 × 1/2 × 4/5 = 4.
The four coprime residues are 1, 3, 7 and 9, which independently confirms the count.
4. Euler's theorem and a large-power remainder
Euler's theorem says that if gcd(a, n) = 1, then
a^φ(n) ≡ 1 (mod n).
Now find 7¹⁰⁰ mod 10. We have gcd(7, 10) = 1 and φ(10) = 4, so
7⁴ ≡ 1 (mod 10).
Since 100 = 4 × 25,
7¹⁰⁰ = (7⁴)²⁵ ≡ 1²⁵ = 1 (mod 10).
Therefore the remainder, and the last digit of 7¹⁰⁰, is 1.
You can check this by listing one full cycle: 7¹ ≡ 7, 7² ≡ 9, 7³ ≡ 3 and 7⁴ ≡ 1 (mod 10). Multiplying by 7 starts the same four-term cycle again. Because 100 is divisible by 4, the exponent lands on the fourth position, whose residue is 1.
Fermat's little theorem is the prime-modulus special case. If p is prime and p does not divide a, then a^(p - 1) ≡ 1 (mod p).
5. Modular inverses and a solved inverse
The modular inverse of a modulo n is a value x satisfying
ax ≡ 1 (mod n).
It exists if and only if gcd(a, n) = 1. The extended Euclidean algorithm finds it in general. For a prime modulus p, Fermat gives a convenient identity:
a^(p - 2) ≡ a^(-1) (mod p).
Find the inverse of 3 modulo 7. Since 7 is prime and does not divide 3,
3^(-1) ≡ 3^(7 - 2) = 3⁵ (mod 7).
Now 3⁵ = 243, and
243 = 7 × 34 + 5.
Therefore 3⁵ ≡ 5 (mod 7), so the inverse is 5. Check it directly:
3 × 5 = 15 = 7 × 2 + 1,
which means 3 × 5 ≡ 1 (mod 7).
Inverses are modular division. Their algebraic meaning is clearer in Group Theory and Algebraic Structures: Groups, Rings and Fields Explained, especially when studying the invertible elements modulo n.
6. The traps GATE builds these on
Reducing the exponent modulo n. Euler's theorem uses φ(n), not n, and only under its coprimality condition.
Ignoring gcd(a, n). If gcd(a, n) ≠ 1, Euler's conclusion cannot simply be applied.
Using totient multiplicativity on non-coprime factors. Although 12 = 4 × 3 works because gcd(4, 3) = 1, the split 12 = 6 × 2 does not justify φ(12) = φ(6)φ(2).
Cancelling without an inverse. From ax ≡ ay (mod n), cancellation of a is valid only when a is invertible modulo n, or after handling the relevant gcd carefully.
Before using a theorem, write its condition beside it. That small step prevents most modular-arithmetic errors.
7. How GATE tests this and the official pointer
Expect large-power remainders, last digits, GCD calculations, counts of coprime integers and inverse-existence questions. Some MSQs mix a true theorem with a missing condition, so checking gcd is as important as exponent manipulation.
These tools sit within Discrete Mathematics and number theory. The organising IIT defines the current syllabus scope and any mark distribution on the official GATE portal. Do not plan around a remembered weightage.
The practice bank contains 1,300+ Discrete Mathematics questions for building speed. Work topic sets in the Engineering Mathematics course, and use the GATE category to connect this toolkit with the wider exam.
8. Key rules and practice
Reduce values early, use Euclid for GCD, compute φ(n) from distinct prime divisors, and apply Euler's theorem only when gcd(a, n) = 1. For 7¹⁰⁰ mod 10, φ(10) = 4 and 100 is a multiple of 4, so the answer is 1. The inverse of 3 modulo 7 is 5 because 3 × 5 ≡ 1.
Practice these four calculations independently: gcd(1071, 462), φ(36), 7¹⁰⁰ mod 10 and 3^(-1) mod 7. Then move to timed number-theory sets in GATE Guidance by Sanchit Sir. Speed will follow once theorem conditions become automatic.
