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

Updated 16 Nov 20266 min read
Number-Theoretic Algorithms for GATE CS: Modular Arithmetic, GCD and Primality Tests

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

O(log min(a,b))

Inverse modulo m

Extended Euclid

gcd(a,m) = 1

O(log min(a,m))

a^e mod m

Binary exponentiation

m > 0, e ≥ 0

O(log e) modular multiplications

Exact test of one n

Trial division

Through floor(sqrt(n))

O(sqrt(n))

Primes through N

Sieve of Eratosthenes

N ≥ 2

O(N log log N) time, O(N) space

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

252 = 1(198) + 54

18 = 54 - 36

198 = 3(54) + 36

18 = 54 - (198 - 3(54)) = 4(54) - 198

54 = 1(36) + 18

18 = 4(252 - 198) - 198 = 4(252) - 5(198)

36 = 2(18) + 0

Therefore 18 = 4(252) - 5(198) certifies the GCD.

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

Square-and-multiply trace for 7^123 mod 13, ending with residue 5.

Write 123 = 64 + 32 + 16 + 8 + 2 + 1 = (1111011)_2. Repeated squaring gives:

Power

1

2

4

8

16

32

64

7^power mod 13

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.

Code
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.

Square-and-multiply table for 7^123 mod 13, listing residues for powers 1 to 64, the running products, and the final answer 5.

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 -17 mod 5 as -2

It is not canonical.

Report 3.

Cancel in 6x ≡ 9 (mod 15)

gcd(6,15) = 3; no inverse exists.

Divide throughout by 3: 2x ≡ 3 (mod 5), so x ≡ 4, 9, 14 (mod 15).

Declare 341 prime after a Fermat pass

Pseudoprimes can pass.

Use factorisation or a Miller-Rabin witness.

Stop below floor(sqrt(n))

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

GATE Test Series

Full-length mocks, topic-wise tests and solutions with performance analysis.

Adjacent revision

Graph Algorithms: BFS, DFS and Shortest Paths

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.