Unit 3: Number Theory-III - Subjective Questions

MTH381 — Number Theory And Cryptography • Practice Questions with Detailed Answers

20 questions

Define a linear congruence. Explain the condition under which the linear congruence $ax \equiv b \pmod{m}$ has a solution.

Solve the linear congruence $7x \equiv 3 \pmod{26}$ and find all incongruent solutions.

State and prove the Chinese Remainder Theorem (CRT).

Using the Chinese Remainder Theorem, solve the following system of congruences:

$x \equiv 2 \pmod{3}, \quad x \equiv 3 \pmod{5}, \quad x \equiv 2 \pmod{7}$

State and prove Fermat's Little Theorem.

Using Fermat's Little Theorem, find the remainder when $3^{100}$ is divided by $7$ .

Explain how computer arithmetic with large integers is performed. Discuss the representation of large integers and the concept of modular arithmetic in this context.

Describe the square-and-multiply (fast modular exponentiation) algorithm and illustrate it by computing $7^{13} \bmod 11$ .

Fast Modular Exponentiation computes $a^e \bmod m$ efficiently by using the binary representation of the exponent, avoiding the computation of the full power.

Algorithm (Square-and-Multiply):

Write the exponent $e$ in binary: $e = (b_{k} b_{k-1} \cdots b_1 b_0)_2$ .
Initialize result = 1.
Scan bits from most significant to least significant:
- Square: result = result^2 mod m
- If the current bit is $1$ : Multiply: result = result * a mod m
The final result is $a^e \bmod m$ .

This reduces the number of multiplications from $O(e)$ to $O(\log_2 e)$ .

Example: Compute $7^{13} \bmod 11$ .

Binary of $13 = (1101)_2$ .

Bit	Operation	result
Start	—	1
1	Square (1) → 1; Multiply → $1 \cdot 7 = 7$	7
1	Square → $49 \equiv 5$ ; Multiply → $5 \cdot 7 = 35 \equiv 2$	2
0	Square → $4$ ; (no multiply)	4
1	Square → $16 \equiv 5$ ; Multiply → $5 \cdot 7 = 35 \equiv 2$	2

Answer: $7^{13} \equiv 2 \pmod{11}$ .

Verification via Fermat: $7^{10} \equiv 1 \pmod{11}$ , so $7^{13} \equiv 7^3 = 343 = 31 \cdot 11 + 2 \equiv 2 \pmod{11}$ . ✓

Distinguish between a congruence and a linear congruence. Give suitable examples of each.

Congruence:

Two integers $a$ and $b$ are said to be congruent modulo $m$ (where $m > 0$ ) if $m$ divides $(a - b)$ . Written as:

$a \equiv b \pmod{m} \iff m \mid (a - b)$

It is a general relation expressing that two numbers leave the same remainder when divided by $m$ .

Example: $17 \equiv 5 \pmod{12}$ because $12 \mid (17 - 5) = 12$ .

Linear Congruence:

A linear congruence is a specific type of congruence involving an unknown variable to the first power, of the form:

$ax \equiv b \pmod{m}$

Here we seek the values of $x$ that satisfy the relation.

Example: $3x \equiv 4 \pmod{7}$ is a linear congruence whose solution is $x \equiv 6 \pmod 7$ .

Key Differences:

Aspect	Congruence	Linear Congruence
Nature	A relation between two numbers	An equation to be solved
Unknown	No unknown variable	Contains unknown $x$
Goal	State equivalence	Find solution(s) for $x$
Form	$a \equiv b \pmod m$	$ax \equiv b \pmod m$
Example	$10 \equiv 4 \pmod 6$	$2x \equiv 4 \pmod 6$

Explain various applications of congruences in computer science and daily life with examples.

Solve the system of congruences using CRT: $x \equiv 1 \pmod 4$ , $x \equiv 2 \pmod 5$ , $x \equiv 3 \pmod 7$ .

Define the multiplicative inverse modulo $m$ . Find the multiplicative inverse of $5$ modulo $12$ .

Explain how the Chinese Remainder Theorem is used in computer arithmetic with large integers to speed up computations.

State and explain the converse of Fermat's Little Theorem. Does the converse always hold? Discuss with reference to pseudoprimes.

Solve the linear congruence $15x \equiv 25 \pmod{35}$ and find all its incongruent solutions.

Explain the role of Fermat's Little Theorem in RSA cryptography and in primality testing.

A basket contains eggs. When counted in groups of $3$ , $5$ , and $7$ , the remainders are $2$ , $3$ , and $2$ respectively. Find the least number of eggs in the basket using CRT.

Describe the linear congruential method for generating pseudorandom numbers. What conditions ensure a maximum period?

Prove that if $\gcd(a, m) = 1$ , then the linear congruence $ax \equiv b \pmod m$ has a unique solution modulo $m$ .

Explain how check digits (e.g., in ISBN or credit card numbers) use congruences for error detection. Illustrate with an example.

Question 1

Define a linear congruence. Explain the condition under which the linear congruence $ax \equiv b \pmod{m}$ has a solution.

Tap card to reveal answer

Answer 1

A linear congruence is a congruence of the form:

$ax \equiv b \pmod{m}$

where $a$ , $b$ , and $m$ are integers with $m > 0$ , and $x$ is the unknown to be determined.

Condition for Solvability:

Let $d = \gcd(a, m)$ . Then:

The congruence $ax \equiv b \pmod{m}$ has a solution if and only if $d \mid b$ (i.e., $d$ divides $b$ ).
If $d \mid b$ , then there are exactly $d$ incongruent solutions modulo $m$ .
If $d \nmid b$ , then the congruence has no solution.

Explanation:

The congruence $ax \equiv b \pmod{m}$ is equivalent to the linear Diophantine equation:

$ax - my = b$

By the theory of Diophantine equations, this has integer solutions if and only if $\gcd(a,m) \mid b$ .

Example: $6x \equiv 4 \pmod{8}$ . Here $d = \gcd(6,8) = 2$ and $2 \mid 4$ , so solutions exist (exactly 2 incongruent solutions modulo 8).

Tap card to flip back

Question 3

State and prove the Chinese Remainder Theorem (CRT).

Tap card to reveal answer

Answer 3

Statement:

Let $m_1, m_2, \ldots, m_n$ be positive integers that are pairwise relatively prime (i.e., $\gcd(m_i, m_j) = 1$ for $i \neq j$ ). Then the system of congruences:

$x \equiv a_1 \pmod{m_1}$
$x \equiv a_2 \pmod{m_2}$
$\vdots$
$x \equiv a_n \pmod{m_n}$

has a unique solution modulo $M = m_1 m_2 \cdots m_n$ .

Proof (Constructive):

Let $M = m_1 m_2 \cdots m_n$ and define $M_k = M / m_k$ for each $k$ .

Since the $m_i$ are pairwise coprime, $\gcd(M_k, m_k) = 1$ .
Therefore, an inverse $y_k$ of $M_k$ modulo $m_k$ exists such that $M_k y_k \equiv 1 \pmod{m_k}$ .

Construct the solution:

$x = \sum_{k=1}^{n} a_k M_k y_k$

Verification: For each $j$ , when we reduce $x$ modulo $m_j$ , every term $M_k y_k$ with $k \neq j$ contains the factor $m_j$ (since $m_j \mid M_k$ ), so it vanishes. Thus:

$x \equiv a_j M_j y_j \equiv a_j \cdot 1 \equiv a_j \pmod{m_j}$

So $x$ satisfies all congruences.

Uniqueness: Suppose $x_1$ and $x_2$ are both solutions. Then $x_1 \equiv x_2 \pmod{m_k}$ for all $k$ , so $m_k \mid (x_1 - x_2)$ . Since the $m_k$ are pairwise coprime, $M \mid (x_1 - x_2)$ , giving $x_1 \equiv x_2 \pmod{M}$ . Hence the solution is unique modulo $M$ . $\blacksquare$

Tap card to flip back

Question 7

Explain how computer arithmetic with large integers is performed. Discuss the representation of large integers and the concept of modular arithmetic in this context.

Tap card to reveal answer

Answer 7

Large Integer Arithmetic deals with performing arithmetic operations on integers that exceed the native word size of a computer (typically 32 or 64 bits).

Representation of Large Integers:

Large integers are represented in a chosen base $b$ (radix), such as $b = 2^{32}$ or $b = 10^9$ .
An integer $n$ is stored as an array of digits $(a_k, a_{k-1}, \ldots, a_1, a_0)$ where:

$n = a_k b^k + a_{k-1} b^{k-1} + \cdots + a_1 b + a_0, \quad 0 \le a_i < b$

This is called a multiple-precision or arbitrary-precision representation.

Basic Operations:

Addition/Subtraction: Digit-by-digit with carry/borrow propagation, complexity $O(n)$ where $n$ is the number of digits.
Multiplication: Schoolbook method is $O(n^2)$ ; faster algorithms like Karatsuba ( $O(n^{1.585})$ ) and FFT-based methods ( $O(n \log n)$ ) exist.
Division: Long division algorithm, more complex to implement.

Modular Arithmetic with Large Integers:

In cryptography (e.g., RSA), computations are done modulo a large integer $m$ :

Modular exponentiation $a^e \bmod m$ is central and computed efficiently using fast (binary) exponentiation / square-and-multiply, reducing the count of multiplications to $O(\log e)$ .
Intermediate results are always reduced modulo $m$ to keep numbers manageable.

Why It Matters:

Cryptographic systems (RSA, Diffie-Hellman) use integers of 1024–4096 bits, far beyond native hardware capacity.
Efficient large-integer arithmetic is essential for the practicality of these systems.

Tap card to flip back

Question 8

Describe the square-and-multiply (fast modular exponentiation) algorithm and illustrate it by computing $7^{13} \bmod 11$ .

Tap card to reveal answer

Answer 8

Fast Modular Exponentiation computes $a^e \bmod m$ efficiently by using the binary representation of the exponent, avoiding the computation of the full power.

Algorithm (Square-and-Multiply):

Write the exponent $e$ in binary: $e = (b_{k} b_{k-1} \cdots b_1 b_0)_2$ .
Initialize result = 1.
Scan bits from most significant to least significant:
- Square: result = result^2 mod m
- If the current bit is $1$ : Multiply: result = result * a mod m
The final result is $a^e \bmod m$ .

This reduces the number of multiplications from $O(e)$ to $O(\log_2 e)$ .

Example: Compute $7^{13} \bmod 11$ .

Binary of $13 = (1101)_2$ .

Bit	Operation	result
Start	—	1
1	Square (1) → 1; Multiply → $1 \cdot 7 = 7$	7
1	Square → $49 \equiv 5$ ; Multiply → $5 \cdot 7 = 35 \equiv 2$	2
0	Square → $4$ ; (no multiply)	4
1	Square → $16 \equiv 5$ ; Multiply → $5 \cdot 7 = 35 \equiv 2$	2

Answer: $7^{13} \equiv 2 \pmod{11}$ .

Verification via Fermat: $7^{10} \equiv 1 \pmod{11}$ , so $7^{13} \equiv 7^3 = 343 = 31 \cdot 11 + 2 \equiv 2 \pmod{11}$ . ✓

Tap card to flip back

Question 9

Distinguish between a congruence and a linear congruence. Give suitable examples of each.

Tap card to reveal answer

Answer 9

Congruence:

Two integers $a$ and $b$ are said to be congruent modulo $m$ (where $m > 0$ ) if $m$ divides $(a - b)$ . Written as:

$a \equiv b \pmod{m} \iff m \mid (a - b)$

It is a general relation expressing that two numbers leave the same remainder when divided by $m$ .

Example: $17 \equiv 5 \pmod{12}$ because $12 \mid (17 - 5) = 12$ .

Linear Congruence:

A linear congruence is a specific type of congruence involving an unknown variable to the first power, of the form:

$ax \equiv b \pmod{m}$

Here we seek the values of $x$ that satisfy the relation.

Example: $3x \equiv 4 \pmod{7}$ is a linear congruence whose solution is $x \equiv 6 \pmod 7$ .

Key Differences:

Aspect	Congruence	Linear Congruence
Nature	A relation between two numbers	An equation to be solved
Unknown	No unknown variable	Contains unknown $x$
Goal	State equivalence	Find solution(s) for $x$
Form	$a \equiv b \pmod m$	$ax \equiv b \pmod m$
Example	$10 \equiv 4 \pmod 6$	$2x \equiv 4 \pmod 6$

Tap card to flip back

Question 10

Explain various applications of congruences in computer science and daily life with examples.

Tap card to reveal answer

Answer 10

Congruences have wide-ranging practical applications. Some important ones include:

1. Hashing Functions:

Hash functions map keys to memory locations using:

$h(k) = k \bmod m$

Used in hash tables for efficient data storage and retrieval.

2. Pseudorandom Number Generation:

The linear congruential generator (LCG) produces sequences via:

$x_{n+1} = (a x_n + c) \bmod m$

Widely used in simulations and games.

3. Check Digits (Error Detection):

ISBN codes use congruences modulo 11 (ISBN-10) or 10 (ISBN-13) to detect errors.
UPC bar codes and credit card numbers use the Luhn algorithm based on modular arithmetic.

4. Cryptography:

RSA encryption relies on modular exponentiation and Euler/Fermat theorems.
Diffie-Hellman key exchange uses modular arithmetic.

5. Calendar Computations:

Determining the day of the week using Zeller's congruence:

$\text{day} = (q + \lfloor \ldots \rfloor + \ldots) \bmod 7$

6. Scheduling and Cyclic Problems:

Problems involving repeating cycles (clock arithmetic, round-robin schedules) use modular arithmetic. For example, $10$ hours after $8$ o'clock is $(8+10) \bmod 12 = 6$ o'clock.

7. Parity Checks:

Detecting even/odd via $n \bmod 2$ for error checking in data transmission.

Tap card to flip back

Question 13

Explain how the Chinese Remainder Theorem is used in computer arithmetic with large integers to speed up computations.

Tap card to reveal answer

Answer 13

The Chinese Remainder Theorem (CRT) provides a powerful technique for performing arithmetic on very large integers by breaking them into smaller, manageable pieces.

The Core Idea — Modular Representation:

Choose a set of pairwise coprime moduli $m_1, m_2, \ldots, m_n$ with product $M = m_1 m_2 \cdots m_n$ . Any integer $x$ with $0 \le x < M$ can be uniquely represented by its residues:

$x \leftrightarrow (x \bmod m_1, \; x \bmod m_2, \; \ldots, \; x \bmod m_n)$

This is called the residue number system (RNS).

How It Speeds Up Computation:

Parallel arithmetic: To compute $x + y$ , $x - y$ , or $x \cdot y$ , we operate on each residue independently:

$(x \cdot y) \bmod m_i = ((x \bmod m_i) \cdot (y \bmod m_i)) \bmod m_i$

Each component can be computed in parallel and involves only small integers (fitting in a machine word).

No carry propagation: Unlike standard multi-precision arithmetic, RNS operations have no inter-digit carries, allowing fully independent parallel processing.
Reconstruction: After computing the result's residues, CRT reconstructs the actual large integer.

Advantages:

Converts one large operation into several small, parallel operations.
Ideal for hardware and cryptographic implementations (e.g., RSA decryption uses CRT to gain roughly a 4× speedup).

Limitations:

Division and comparison are difficult in RNS.
Conversion overhead between representations.

RSA Example: In RSA, decryption $m = c^d \bmod n$ where $n = pq$ is computed separately modulo $p$ and $q$ , then combined via CRT — significantly faster than direct computation modulo $n$ .

Tap card to flip back

Question 14

State and explain the converse of Fermat's Little Theorem. Does the converse always hold? Discuss with reference to pseudoprimes.

Tap card to reveal answer

Answer 14

Fermat's Little Theorem (Recap):

If $p$ is prime and $\gcd(a, p) = 1$ , then $a^{p-1} \equiv 1 \pmod p$ .

Converse Statement:

The converse would state: If $a^{n-1} \equiv 1 \pmod n$ for some $a$ with $\gcd(a, n) = 1$ , then $n$ is prime.

Does the Converse Hold?

No, the converse is FALSE in general. There exist composite numbers $n$ that satisfy the Fermat congruence for certain bases $a$ . Such numbers are called pseudoprimes.

Pseudoprimes:

A composite integer $n$ is called a pseudoprime to the base $a$ if:

$a^{n-1} \equiv 1 \pmod n$

Example: $341 = 11 \times 31$ is composite, yet $2^{340} \equiv 1 \pmod{341}$ . So $341$ is a pseudoprime to base $2$ .

Carmichael Numbers (Absolute Pseudoprimes):

Some composite numbers are pseudoprimes to every base $a$ coprime to $n$ . These are called Carmichael numbers.

Smallest example: $561 = 3 \times 11 \times 17$ . For every $a$ with $\gcd(a, 561) = 1$ , $a^{560} \equiv 1 \pmod{561}$ .

Significance:

Fermat's theorem gives a necessary but not sufficient condition for primality.
It forms the basis of the Fermat primality test, which is probabilistic and can be fooled by Carmichael numbers.
This limitation led to stronger tests like the Miller-Rabin primality test.

Tap card to flip back

Question 16

Explain the role of Fermat's Little Theorem in RSA cryptography and in primality testing.

Tap card to reveal answer

Answer 16

Fermat's Little Theorem is a foundational result underpinning modern cryptography.

1. Role in RSA Cryptography:

In RSA, we choose two primes $p$ and $q$ , let $n = pq$ , and select public/private key exponents $e$ and $d$ such that:

$ed \equiv 1 \pmod{\phi(n)}$

The correctness of RSA decryption — that $(m^e)^d \equiv m \pmod n$ — is proven using Fermat's Little Theorem (generalized as Euler's theorem).

Proof sketch: Since $ed \equiv 1 \pmod{\phi(n)}$ , write $ed = 1 + k\phi(n)$ . Working modulo $p$ (a prime factor of $n$ ), Fermat's theorem gives $m^{p-1} \equiv 1 \pmod p$ , so:

$m^{ed} = m^{1 + k(p-1)(q-1)} \equiv m \pmod p$

Similarly modulo $q$ , and by CRT, $m^{ed} \equiv m \pmod n$ . This guarantees decryption recovers the original message.

2. Role in Primality Testing (Fermat Primality Test):

The theorem gives a way to test whether a number $n$ is prime:

Pick a random base $a$ with $1 < a < n$ .
Compute $a^{n-1} \bmod n$ .
If $a^{n-1} \not\equiv 1 \pmod n$ , then $n$ is definitely composite.
If $a^{n-1} \equiv 1 \pmod n$ , then $n$ is probably prime (may still be a pseudoprime).

Limitations:

Fails for Carmichael numbers (e.g., 561), which pass the test for all bases despite being composite.
This weakness motivated stronger probabilistic tests like Miller-Rabin.

Summary: Fermat's Little Theorem ensures RSA works correctly and provides a fast, though imperfect, primality-checking method essential for generating cryptographic keys.

Tap card to flip back

Question 18

Describe the linear congruential method for generating pseudorandom numbers. What conditions ensure a maximum period?

Tap card to reveal answer

Answer 18

Linear Congruential Generator (LCG):

The LCG is one of the oldest and simplest algorithms for generating a sequence of pseudorandom numbers. It is defined by the recurrence relation:

$x_{n+1} = (a x_n + c) \bmod m$

where:

$m$ = modulus ( $m > 0$ )
$a$ = multiplier ( $0 < a < m$ )
$c$ = increment ( $0 \le c < m$ )
$x_0$ = seed or starting value ( $0 \le x_0 < m$ )

Each generated $x_n$ lies in the range $[0, m-1]$ . To obtain numbers in $[0, 1)$ , we compute $x_n / m$ .

Special Case: When $c = 0$ , it is called a multiplicative congruential generator.

Example: With $m = 9$ , $a = 7$ , $c = 4$ , $x_0 = 3$ :

$x_1 = (7 \cdot 3 + 4) \bmod 9 = 25 \bmod 9 = 7$
$x_2 = (7 \cdot 7 + 4) \bmod 9 = 53 \bmod 9 = 8$
$x_3 = (7 \cdot 8 + 4) \bmod 9 = 60 \bmod 9 = 6$ ...

Conditions for Maximum Period (Hull-Dobell Theorem):

The LCG achieves the full period $m$ (all residues occur before repetition) if and only if:

$\gcd(c, m) = 1$ (i.e., $c$ and $m$ are coprime).
$a - 1$ is divisible by every prime factor of $m$ .
$a - 1$ is divisible by $4$ if $m$ is divisible by $4$ .

Importance:

A longer period means the sequence appears more random before repeating.
Poor choices of parameters lead to short periods and detectable patterns, making the generator unsuitable for cryptography.

Tap card to flip back

Question 19

Prove that if $\gcd(a, m) = 1$ , then the linear congruence $ax \equiv b \pmod m$ has a unique solution modulo $m$ .

Tap card to reveal answer

Answer 19

Claim: If $\gcd(a, m) = 1$ , then $ax \equiv b \pmod m$ has exactly one solution modulo $m$ .

Proof:

Part 1: Existence of a solution.

Since $\gcd(a, m) = 1$ , by Bézout's identity there exist integers $s$ and $t$ such that:

$as + mt = 1$

Reducing modulo $m$ :

$as \equiv 1 \pmod m$

Thus $s = a^{-1}$ is the multiplicative inverse of $a$ modulo $m$ . Multiplying both sides of $ax \equiv b \pmod m$ by $s$ :

$s(ax) \equiv sb \pmod m$
$(sa)x \equiv sb \pmod m$
$1 \cdot x \equiv sb \pmod m$
$x \equiv sb \pmod m$

So $x \equiv sb \pmod m$ is a solution, proving existence.

Part 2: Uniqueness of the solution.

Suppose $x_1$ and $x_2$ are both solutions. Then:

$a x_1 \equiv b \pmod m \quad \text{and} \quad a x_2 \equiv b \pmod m$

Subtracting:

$a(x_1 - x_2) \equiv 0 \pmod m$

This means $m \mid a(x_1 - x_2)$ . Since $\gcd(a, m) = 1$ , $m$ must divide $(x_1 - x_2)$ :

$m \mid (x_1 - x_2) \implies x_1 \equiv x_2 \pmod m$

Hence any two solutions are congruent modulo $m$ , so the solution is unique modulo $m$ . $\blacksquare$

Tap card to flip back

Question 20

Explain how check digits (e.g., in ISBN or credit card numbers) use congruences for error detection. Illustrate with an example.

Tap card to reveal answer

Answer 20

Check Digits are extra digits appended to identification numbers, computed using modular arithmetic, to detect common errors such as single-digit mistakes and transposition of adjacent digits.

General Principle:

A check digit is chosen so that a weighted sum of all digits satisfies a specific congruence modulo some integer.

Example 1: ISBN-10 (modulo 11)

An ISBN-10 number $d_1 d_2 \cdots d_{10}$ must satisfy:

$\sum_{i=1}^{10} i \cdot d_i \equiv 0 \pmod{11}$

The last digit $d_{10}$ is the check digit (which may be $X$ representing $10$ ).

Illustration: For ISBN $0-306-40615-?$ , digits are $0,3,0,6,4,0,6,1,5$ . Compute the weighted sum of the first nine:

$1(0)+2(3)+3(0)+4(6)+5(4)+6(0)+7(6)+8(1)+9(5)$
$= 0+6+0+24+20+0+42+8+45 = 145$

We need $145 + 10 d_{10} \equiv 0 \pmod{11}$ . Since $145 \equiv 2 \pmod{11}$ and $10 \equiv -1 \pmod{11}$ :

$2 - d_{10} \equiv 0 \pmod{11} \Rightarrow d_{10} = 2$

So the check digit is $2$ .

Example 2: Credit Cards (Luhn Algorithm, modulo 10)

Starting from the rightmost digit, double every second digit.
If doubling gives a two-digit number, subtract $9$ (or add the digits).
Sum all digits. The number is valid if the total $\equiv 0 \pmod{10}$ .

Error Detection Capability:

Single-digit errors: Always detected (changing one digit changes the sum).
Transposition errors: ISBN-10 (mod 11) detects all adjacent transpositions; the Luhn scheme detects most.

Conclusion: Congruences provide a simple, efficient mechanism to validate identification numbers and catch data-entry errors.

Tap card to flip back

1 / 20

Unit2 Unit4

Unit 3: Number Theory-III - Subjective Questions

Did this save you a night before the exam?