Number-Theoretic Algorithms for GATE CS: Modular Arithmetic, GCD and Primality Tests
Build a reliable number-theory toolkit through fixed examples: residues, Euclid and inverses, fast modular powers, exact primality checks and witness tests.
KnowledgeGate Team
Exam prep & CS education

Modular arithmetic, GCD and primality get revised as separate topics, yet one question can ask you to combine them and to justify the precondition each step needs. The costly errors are reporting a negative remainder as the answer, dividing when no inverse exists, and accepting a Fermat pass as proof of primality. Redo each calculation from memory after working through it.
Number-theoretic algorithms: choose the right tool
The statement a ≡ b (mod m) means m divides a - b; gcd(a,b) is the greatest positive divisor of both. An inverse modulo m exists iff gcd(a,m) = 1. Modular exponentiation finds a^e mod m without constructing the power. A primality test handles one integer; a sieve covers a range.
Task | Tool | Required condition | Cost in the unit-cost model |
|---|---|---|---|
GCD | Euclid | Positive integers |
|
Inverse modulo | Extended Euclid |
|
|
| Binary exponentiation |
|
|
Exact test of one | Trial division | Through |
|
Primes through | Sieve of Eratosthenes |
|
|
The GATE CS Exam category page places these algorithms within the wider paper so you can connect this arithmetic to adjacent revision topics.
Modular arithmetic: reduce early and keep a canonical residue
Canonical residues lie from 0 to m - 1. Here -17 mod 5 = 3 because -17 = (-4)(5) + 3. Reduce early: 38 ≡ -1 and 47 ≡ 8, so (38 × 47) mod 13 = -8 mod 13 = 5.
Addition, subtraction and multiplication preserve congruence. Cancelling c unchanged requires gcd(c,m) = 1. Normalise a negative program remainder with ((r % m) + m) % m. Avoid a × b overflow with a wider type, arbitrary precision or safe modular multiplication.
Extended Euclid: GCD and modular inverse
Euclid gives gcd(252,198) = 18; back-substitution certifies it.
Euclidean quotient and remainder | Back-substituted linear combination |
|---|---|
|
|
|
|
|
|
| Therefore |
For an inverse, 43 = 2(17) + 9, 17 = 1(9) + 8, and 9 = 1(8) + 1. Thus 1 = 9 - 8 = 2(9) - 17 = 2(43) - 5(17). The inverse of 17 mod 43 is -5 ≡ 38, verified by 17 × 38 = 646 = 15(43) + 1.
Fast modular exponentiation: 7^123 mod 13

Write 123 = 64 + 32 + 16 + 8 + 2 + 1 = (1111011)_2. Repeated squaring gives:
Power | 1 | 2 | 4 | 8 | 16 | 32 | 64 |
|---|---|---|---|---|---|---|---|
| 7 | 10 | 9 | 3 | 9 | 3 | 9 |
For set bits, 9 × 3 ≡ 1, 1 × 9 ≡ 9, 9 × 3 ≡ 1, 1 × 10 ≡ 10, and 10 × 7 ≡ 5. Hence 7^123 mod 13 = 5.
result=1; base=7; exponent=123
while exponent>0:
if odd(exponent): result=(result × base) mod 13
base=(base × base) mod 13
exponent=floor(exponent/2)Reducing after every multiplication and square gives O(log 123) iterations.

Primality testing: exact division, Fermat's trap and a witness
For 221, floor(sqrt(221)) = 14, so test only 2, 3, 5, 7, 11, 13. Since 221 = 13 × 17, it is composite. Larger factors pair below the square root. Use a sieve for every prime up to a limit.
Fermat alone is not proof: 341 = 11 × 31, yet 2^10 = 1024 = 3(341) + 1, so 2^340 ≡ 1 (mod 341). It is a base-2 Fermat pseudoprime.
For Miller-Rabin, 340 = 2^2 × 85 and x = 2^85 mod 341 = 32, neither 1 nor 340. Squaring gives 32^2 mod 341 = 1 without reaching -1 ≡ 340, so base 2 witnesses compositeness. A pass means probable prime under the chosen bases; a witness proves composite.
For any odd n > 2, write n - 1 = 2^s d with d odd. For a chosen base a, compute x = a^d mod n. That base passes if x is 1 or n - 1; otherwise square x at most s - 1 times, passing only if n - 1 appears. Reaching 1 first, as 32 does for 341, exposes a non-trivial square root of 1 and proves compositeness.
The earlier Randomized Algorithms Explained owns the Las Vegas versus Monte Carlo distinction and error amplification. The focus here is different: the modular arithmetic inside one Fermat or Miller-Rabin trial and exactly what its residues prove.
Number-theory traps: check preconditions
Trap | What goes wrong | Correction |
|---|---|---|
Report | It is not canonical. | Report |
Cancel in |
| Divide throughout by |
Declare | Pseudoprimes can pass. | Use factorisation or a Miller-Rabin witness. |
Stop below | An equal factor can be missed. | Include the bound. |
Rapid checks: 12 has no inverse modulo 18 because the GCD is 6; (-29)^2 mod 7 = 1 because -29 ≡ -1; and 97 is prime after testing primes 2, 3, 5, 7 through sqrt(97).
GATE CS number-theory questions: combine the preconditions with the calculation
A question may not name the required algorithm. Translate each phrase into a test: inverse or cancellation means find the GCD first; a large exponent modulo m means repeated squaring; prove composite means produce a factor or a witness; probably prime permits a stated probabilistic test. A Fermat pass never reverses the burden of proof.
For example, solve 17x ≡ 9 (mod 43). Since gcd(17,43) = 1, the inverse 38 exists, so x ≡ 9(38) ≡ 342 ≡ 41 (mod 43). Substitution checks the result: 17(41) = 697 = 16(43) + 9. By contrast, 12x ≡ 8 (mod 18) has no solution because gcd(12,18) = 6 does not divide 8. Cancelling before that check would invent answers.
For complexity comparisons, name the model. Euclid takes O(log min(a,b)) divisions, binary exponentiation takes O(log e) modular multiplications, trial division takes O(sqrt(n)) candidate checks, and the sieve takes O(N log log N) arithmetic work plus O(N) storage in the unit-cost model. Operand bit lengths require a finer analysis.
Number-theoretic algorithms: a 90-minute revision route
Spend 25 minutes on residues, Euclid and inverses; 25 on the 7^123 mod 13 table; 25 classifying 221 and 341; and 15 redoing traps. Next day, repeat errors and explain each precondition aloud.
Learning need | Where to go | What to do there |
|---|---|---|
Core concepts | Worked traces | Redo every worked trace without looking. |
Broader navigation | GATE CS Exam category | Map related topics. |
Practice and diagnosis | Full-length mocks, topic-wise tests and solutions with performance analysis. | |
Adjacent revision | Contrast graph and arithmetic choices. |
The short version: normalise residues, check the GCD before inversion or cancellation, and use repeated squaring. Separate a witness from a probable-prime pass, then choose trial division for one number or a sieve for a range.
Keep learning
Modular Arithmetic for GATE CS: Congruences, GCD and Euler's Totient, Solved
Turn large remainder questions into small calculations using congruences, the Euclidean algorithm, Euler's totient and modular inverses.
Shortest Path Algorithms: Dijkstra, Bellman-Ford and Floyd-Warshall with Worked Examples for GATE CS
Learn the relaxation idea behind shortest paths, trace three core algorithms by hand, and choose the right method from edge weights and source count.
Sorting Algorithms: Complete Guide with Worked Examples for GATE CS and Interviews
Build a reliable sorting toolkit for GATE CS and coding interviews. Compare six core algorithms, follow two worked traces, and learn the traps behind stability, space and pass counts.
Greedy Algorithms for GATE CS: Concepts, Worked Examples, and Where Greedy Fails
Learn when a greedy choice is provably correct, trace Kruskal step by step, and use numeric counterexamples to see why the same idea fails for coin change and 0/1 knapsack.





