Unit 3: GCD and Primality testing - Subjective Questions

CSE329 — Prelude To Competitive Coding • Practice Questions with Detailed Answers

20 questions

Explain the Basic Euclidean algorithm for computing the GCD of two numbers. Illustrate with an example of finding $\gcd(48, 18)$ .

Describe the Extended Euclidean algorithm. How does it help in finding integers $x$ and $y$ such that $ax + by = \gcd(a, b)$ ? Solve for $a = 30$ , $b = 20$ .

Explain how to find the total number of divisors of a number using its prime factorization. Compute the number of divisors of $360$ .

Describe an efficient algorithm to find all prime factors of a number $N$ . Trace it for $N = 84$ .

Explain why prime factorization can be done by iterating only up to the square root of the number. Justify mathematically.

Define K-jagged numbers. Explain their significance and give examples.

Define Stormer numbers. Explain the mathematical condition that characterizes them.

Define a Frugal number and explain the condition using digit counts. Verify whether $125$ is a frugal number.

Define P-smooth numbers. Describe how to find all P-smooth numbers in a given range $[L, R]$ .

State Lemoine's Conjecture and explain it with examples. How does it relate to Goldbach's conjecture?

Distinguish between the Basic Euclidean algorithm and the Extended Euclidean algorithm in terms of purpose, output, and applications.

Comparison of Basic vs Extended Euclidean Algorithm:

Aspect	Basic Euclidean	Extended Euclidean
Purpose	Compute $\gcd(a,b)$	Compute $\gcd(a,b)$ and coefficients $x, y$
Output	A single value (GCD)	GCD plus $x, y$ such that $ax + by = \gcd(a,b)$
Equation	$\gcd(a,b) = \gcd(b, a \bmod b)$	$ax + by = \gcd(a,b)$ (Bézout's identity)
Complexity	$O(\log \min(a,b))$	$O(\log \min(a,b))$
Applications	Simplifying fractions, GCD problems	Modular inverse, Diophantine equations, RSA, CRT

Key difference:

The basic version only tells us the GCD.
The extended version additionally provides the linear combination expressing the GCD, which is essential for modular arithmetic and cryptography.

Example: For $a=30, b=20$ : Basic gives $\gcd = 10$ ; Extended gives $x=1, y=-1$ with $30(1)+20(-1)=10$ .

Explain how the Extended Euclidean algorithm is used to compute the modular multiplicative inverse. Find the inverse of $3$ modulo $11$ .

Derive the recursive relation used in the Extended Euclidean algorithm and explain how the coefficients are updated at each step.

Explain the Sieve of Eratosthenes for primality testing and how it can be adapted to find the smallest prime factor of every number up to $N$ .

Given the number $N = 720$ , find its prime factorization, the total number of divisors, and the sum of divisors.

Compare K-jagged (k-rough) numbers and P-smooth numbers. Highlight their differences with examples.

Both concepts classify numbers based on the size of their prime factors, but from opposite directions.

Aspect	K-jagged (k-rough)	P-smooth
Condition	Smallest prime factor $\ge k$	Largest prime factor $\le P$
Restricts	Small prime factors	Large prime factors
Example ( $k=5$ / $P=5$ )	$5, 7, 25, 35, 49$	$1, 2, 3, 4, 5, 6, 8, 9, 10$
Excludes	Numbers with small factors ( $2,3$ )	Numbers with large factors ( $7,11,\dots$ )

Detailed examples:

5-rough: $49 = 7^2$ (smallest factor $7 \ge 5$ ) ✓; $6=2\times3$ ✗ (factor $2<5$ )
5-smooth: $12 = 2^2 \times 3$ (largest factor $3 \le 5$ ) ✓; $14 = 2 \times 7$ ✗ (factor $7 > 5$ )

Key insight:

Rough numbers avoid small primes.
Smooth numbers avoid large primes.
They are essentially complementary notions in number theory, both widely used in sieve algorithms and cryptographic factorization.

Write an algorithm to determine whether a given number $n$ is prime using the $O(\sqrt{n})$ method. Explain the optimizations used.

Verify whether $n = 5$ is a Störmer number and check the first few Störmer numbers. Explain the verification process.

Recall: $n$ is a Störmer number if the greatest prime factor $P(n^2 + 1) \ge 2n$ .

Verification for $n = 5$ :

Compute $n^2 + 1 = 25 + 1 = 26$ .
Factorize: $26 = 2 \times 13$ .
Greatest prime factor $P(26) = 13$ .
Check: $13 \ge 2 \times 5 = 10$ ? Yes ✓

So $n = 5$ is a Störmer number.

Checking the first few numbers:

$n$	$n^2+1$	Factorization	$P(n^2+1)$	$2n$	Störmer?
1	2	2	2	2	✓
2	5	5	5	4	✓
3	10	2×5	5	6	✗
4	17	17	17	8	✓
5	26	2×13	13	10	✓
6	37	37	37	12	✓
7	50	2×5²	5	14	✗

First few Störmer numbers: $1, 2, 4, 5, 6, 9, 10, \dots$

Solve the following GCD-based problem: Find the GCD of an array $[12, 18, 24, 30]$ and explain the property that allows extending GCD to multiple numbers.

Explain the relationship $\text{LCM}(a, b) \times \gcd(a, b) = a \times b$ and use it to compute the LCM of $24$ and $36$ . Discuss its use in solving problems.

Question 1

Explain the Basic Euclidean algorithm for computing the GCD of two numbers. Illustrate with an example of finding $\gcd(48, 18)$ .

Tap card to reveal answer

Answer 1

The Euclidean algorithm is an efficient method to compute the Greatest Common Divisor (GCD) of two integers.

Principle: It is based on the property that:
$\gcd(a, b) = \gcd(b, a \bmod b)$
The process repeats until the remainder becomes $0$ ; the last non-zero remainder is the GCD.

Steps:

Divide the larger number by the smaller.
Replace the larger number with the smaller, and the smaller with the remainder.
Repeat until remainder is $0$ .

Example — $\gcd(48, 18)$ :

$48 = 18 \times 2 + 12$
$18 = 12 \times 1 + 6$
$12 = 6 \times 2 + 0$

The last non-zero remainder is $6$ , so $\gcd(48, 18) = 6$ .

Time complexity: $O(\log(\min(a, b)))$ , which makes it very efficient.

Tap card to flip back

Question 5

Explain why prime factorization can be done by iterating only up to the square root of the number. Justify mathematically.

Tap card to reveal answer

Answer 5

Key idea: To find prime factors of $N$ , it is sufficient to check divisors only up to $\sqrt{N}$ .

Mathematical justification:

Suppose $N = a \times b$ where $a \le b$ .
Then $a \le \sqrt{N}$ because if both $a$ and $b$ were greater than $\sqrt{N}$ , their product would exceed $N$ :
$a \times b > \sqrt{N} \times \sqrt{N} = N$
which is a contradiction.
Therefore, at least one factor of any factor pair is $\le \sqrt{N}$ .

Consequence:

Once we remove all prime factors $\le \sqrt{N}$ , if the remaining value is greater than $1$ , it must itself be a prime (the single large factor).

Benefit: Reduces time complexity from $O(N)$ to $O(\sqrt{N})$ .

Example: For $N = 97$ , we only test divisors up to $\lfloor\sqrt{97}\rfloor = 9$ . None divide $97$ , so it is prime.

Tap card to flip back

Question 6

Define K-jagged numbers. Explain their significance and give examples.

Tap card to reveal answer

Answer 6

K-jagged numbers (also related to k-rough numbers) are numbers whose smallest prime factor is greater than or equal to a given value $k$ . In some competitive contexts, a number is called k-jagged if all its prime factors are $\ge k$ .

Definition: A positive integer $n$ is k-rough (k-jagged) if every prime factor $p$ of $n$ satisfies $p \ge k$ .

Key points:

$1$ is considered k-rough for any $k$ (vacuously, it has no prime factors).
Larger $k$ means fewer numbers qualify.

Examples ( $k = 5$ ):

$5, 7, 25, 35, 49, 55$ are 5-rough since their smallest prime factor $\ge 5$ .
$6 = 2 \times 3$ is not 5-rough (has factor $2 < 5$ ).

Significance: Used in sieve-based problems, number theory analysis, and generating sequences with restricted small factors.

Tap card to flip back

Question 7

Define Stormer numbers. Explain the mathematical condition that characterizes them.

Tap card to reveal answer

Answer 7

Störmer numbers (or arc-cotangent irreducible numbers) are positive integers $n$ for which the greatest prime factor of $n^2 + 1$ is greater than or equal to $2n$ .

Definition:
A positive integer $n$ is a Störmer number if:
$P(n^2 + 1) \ge 2n$
where $P(m)$ denotes the greatest prime factor of $m$ .

Examples:

$n = 1$ : $n^2 + 1 = 2$ , greatest prime factor $= 2 \ge 2(1) = 2$ ✓ → Störmer number
$n = 2$ : $n^2 + 1 = 5$ , greatest prime factor $= 5 \ge 4$ ✓ → Störmer number
$n = 4$ : $n^2 + 1 = 17$ , greatest prime factor $= 17 \ge 8$ ✓
$n = 3$ : $n^2 + 1 = 10 = 2 \times 5$ , greatest prime factor $= 5 \ge 6$ ? No → not a Störmer number

Significance: They are used in the theory of continued-fraction approximations of $\pi$ using Machin-like formulas.

Tap card to flip back

Question 8

Define a Frugal number and explain the condition using digit counts. Verify whether $125$ is a frugal number.

Tap card to reveal answer

Answer 8

A Frugal number (also called an economical number) is a number that has more digits than the number of digits required to write its prime factorization (including exponents greater than $1$ ).

Condition: A number $N$ is frugal if:
$D(N) > D(\text{prime factorization of } N)$
where $D(x)$ counts the digits, and the prime factorization is written with exponents (exponent $1$ omitted).

Example — $N = 125$ :

Number of digits in $125 = 3$ .
Prime factorization: $125 = 5^3$ .
Digits used in factorization: $5$ and $3$ → $2$ digits.
Since $3 > 2$ , $125$ is a frugal number. ✓

Another Example — $N = 1024$ :

Digits in $1024 = 4$ .
Factorization: $2^{10}$ → digits: $2$ and $10$ → $3$ digits.
Since $4 > 3$ , $1024$ is frugal.

Note: Frugal numbers are relatively rare and are also known as economical numbers.

Tap card to flip back

Question 9

Define P-smooth numbers. Describe how to find all P-smooth numbers in a given range $[L, R]$ .

Tap card to reveal answer

Answer 9

A P-smooth number is a positive integer whose largest prime factor is less than or equal to $P$ .

Definition: An integer $n$ is P-smooth if every prime factor $p$ of $n$ satisfies:
$p \le P$

Examples ( $P = 5$ ):

$8 = 2^3$ → 5-smooth ✓
$15 = 3 \times 5$ → 5-smooth ✓
$14 = 2 \times 7$ → not 5-smooth (has factor $7 > 5$ )

Algorithm to find P-smooth numbers in $[L, R]$ :

For each number in :
- Find its largest prime factor by trial division.
- If the largest prime factor $\le P$ , mark $n$ as P-smooth.

Efficient sieve approach:

Use a modified sieve: for each number, repeatedly divide out primes $\le P$ ; if the result becomes $1$ , the number is P-smooth.

Applications: Cryptography (factorization algorithms like Pollard's $p-1$ ), number theory, and analysis of algorithms.

Tap card to flip back

Question 10

State Lemoine's Conjecture and explain it with examples. How does it relate to Goldbach's conjecture?

Tap card to reveal answer

Answer 10

Lemoine's Conjecture (also known as Levy's Conjecture) states that:

Every odd integer greater than $5$ can be expressed as the sum of a prime and twice a prime.

Mathematical form:
$2n + 1 = p + 2q$
where $p$ and $q$ are primes and $n \ge 3$ .

Examples:

$7 = 3 + 2 \times 2 = 3 + 4$
$9 = 5 + 2 \times 2 = 5 + 4$ ; also $9 = 3 + 2 \times 3$
$11 = 5 + 2 \times 3 = 5 + 6$
$15 = 5 + 2 \times 5 = 5 + 10$ ; also $15 = 11 + 2 \times 2$

Relation to Goldbach's Conjecture:

Goldbach's (strong) conjecture states every even integer $> 2$ is the sum of two primes.
Lemoine's conjecture can be seen as a strengthening related to odd numbers, and is a consequence-type refinement of Goldbach's ideas.
Both remain unproven but verified computationally for large ranges.

Tap card to flip back

Question 11

Distinguish between the Basic Euclidean algorithm and the Extended Euclidean algorithm in terms of purpose, output, and applications.

Tap card to reveal answer

Answer 11

Comparison of Basic vs Extended Euclidean Algorithm:

Aspect	Basic Euclidean	Extended Euclidean
Purpose	Compute $\gcd(a,b)$	Compute $\gcd(a,b)$ and coefficients $x, y$
Output	A single value (GCD)	GCD plus $x, y$ such that $ax + by = \gcd(a,b)$
Equation	$\gcd(a,b) = \gcd(b, a \bmod b)$	$ax + by = \gcd(a,b)$ (Bézout's identity)
Complexity	$O(\log \min(a,b))$	$O(\log \min(a,b))$
Applications	Simplifying fractions, GCD problems	Modular inverse, Diophantine equations, RSA, CRT

Key difference:

The basic version only tells us the GCD.
The extended version additionally provides the linear combination expressing the GCD, which is essential for modular arithmetic and cryptography.

Example: For $a=30, b=20$ : Basic gives $\gcd = 10$ ; Extended gives $x=1, y=-1$ with $30(1)+20(-1)=10$ .

Tap card to flip back

Question 14

Explain the Sieve of Eratosthenes for primality testing and how it can be adapted to find the smallest prime factor of every number up to $N$ .

Tap card to reveal answer

Answer 14

The Sieve of Eratosthenes efficiently finds all primes up to $N$ .

Basic Sieve:

Create a boolean array isPrime[0..N] initialized to true.
Mark $0$ and $1$ as not prime.
For each $i$ from $2$ to $\sqrt{N}$ : if isPrime[i] is true, mark all multiples $i^2, i^2+i, \dots$ as not prime.

Time complexity: $O(N \log \log N)$ .

Smallest Prime Factor (SPF) Sieve:
To record the smallest prime factor of every number:

spf = array of size N+1, initialized to 0
for i = 2 to N:
if spf[i] == 0: // i is prime
for j = i to N step i:
if spf[j] == 0:
spf[j] = i

Usage: Once spf[] is built, any number $n \le N$ can be factorized in $O(\log n)$ by repeatedly dividing by spf[n].

Example: For $n = 60$ : $spf[60]=2 \to 30$ , $spf[30]=2 \to 15$ , $spf[15]=3 \to 5$ , $spf[5]=5 \to 1$ . So $60 = 2^2 \times 3 \times 5$ .

Tap card to flip back

Question 16

Compare K-jagged (k-rough) numbers and P-smooth numbers. Highlight their differences with examples.

Tap card to reveal answer

Answer 16

Both concepts classify numbers based on the size of their prime factors, but from opposite directions.

Aspect	K-jagged (k-rough)	P-smooth
Condition	Smallest prime factor $\ge k$	Largest prime factor $\le P$
Restricts	Small prime factors	Large prime factors
Example ( $k=5$ / $P=5$ )	$5, 7, 25, 35, 49$	$1, 2, 3, 4, 5, 6, 8, 9, 10$
Excludes	Numbers with small factors ( $2,3$ )	Numbers with large factors ( $7,11,\dots$ )

Detailed examples:

5-rough: $49 = 7^2$ (smallest factor $7 \ge 5$ ) ✓; $6=2\times3$ ✗ (factor $2<5$ )
5-smooth: $12 = 2^2 \times 3$ (largest factor $3 \le 5$ ) ✓; $14 = 2 \times 7$ ✗ (factor $7 > 5$ )

Key insight:

Rough numbers avoid small primes.
Smooth numbers avoid large primes.
They are essentially complementary notions in number theory, both widely used in sieve algorithms and cryptographic factorization.

Tap card to flip back

Question 17

Write an algorithm to determine whether a given number $n$ is prime using the $O(\sqrt{n})$ method. Explain the optimizations used.

Tap card to reveal answer

Answer 17

Primality testing determines whether $n$ is prime.

Optimized $O(\sqrt{n})$ Algorithm:

isPrime(n):
if n <= 1: return false
if n <= 3: return true
if n % 2 == 0 or n % 3 == 0: return false
i = 5
while i * i <= n:
if n % i == 0 or n % (i + 2) == 0:
return false
i = i + 6
return true

Optimizations explained:

Check up to $\sqrt{n}$ only: Any factor larger than $\sqrt{n}$ pairs with a smaller factor, so testing beyond $\sqrt{n}$ is redundant.
Handle $2$ and $3$ separately: Then skip all even numbers and multiples of $3$ .
6k ± 1 rule: All primes greater than $3$ are of the form $6k \pm 1$ . So we test only $i$ and $i+2$ , incrementing by $6$ .

Time complexity: $O(\sqrt{n})$ with a small constant factor.

Example: For $n = 97$ : test $i=5$ ( $5\times5=25\le97$ ), $7$ , ... up to $9$ ; none divide $97$ , so $97$ is prime.

Tap card to flip back

Question 18

Verify whether $n = 5$ is a Störmer number and check the first few Störmer numbers. Explain the verification process.

Tap card to reveal answer

Answer 18

Recall: $n$ is a Störmer number if the greatest prime factor $P(n^2 + 1) \ge 2n$ .

Verification for $n = 5$ :

Compute $n^2 + 1 = 25 + 1 = 26$ .
Factorize: $26 = 2 \times 13$ .
Greatest prime factor $P(26) = 13$ .
Check: $13 \ge 2 \times 5 = 10$ ? Yes ✓

So $n = 5$ is a Störmer number.

Checking the first few numbers:

$n$	$n^2+1$	Factorization	$P(n^2+1)$	$2n$	Störmer?
1	2	2	2	2	✓
2	5	5	5	4	✓
3	10	2×5	5	6	✗
4	17	17	17	8	✓
5	26	2×13	13	10	✓
6	37	37	37	12	✓
7	50	2×5²	5	14	✗

First few Störmer numbers: $1, 2, 4, 5, 6, 9, 10, \dots$

Tap card to flip back

Question 19

Solve the following GCD-based problem: Find the GCD of an array $[12, 18, 24, 30]$ and explain the property that allows extending GCD to multiple numbers.

Tap card to reveal answer

Answer 19

Property: The GCD of multiple numbers can be computed iteratively using the associative property:
$\gcd(a, b, c) = \gcd(\gcd(a, b), c)$

This works because the set of common divisors of all numbers is preserved when computing pairwise GCDs progressively.

Solution for $[12, 18, 24, 30]$ :

:
- $18 = 12 \times 1 + 6$
- $12 = 6 \times 2 + 0 \Rightarrow \gcd = 6$
:
- $24 = 6 \times 4 + 0 \Rightarrow \gcd = 6$
:
- $30 = 6 \times 5 + 0 \Rightarrow \gcd = 6$

Result: $\gcd(12, 18, 24, 30) = \mathbf{6}$ .

Algorithm:

result = arr[0]
for i = 1 to n-1:
result = gcd(result, arr[i])
if result == 1: break // optimization
return result

Optimization: If the running GCD becomes $1$ , we can stop early since $1$ divides everything.

Tap card to flip back

Question 20

Explain the relationship $\text{LCM}(a, b) \times \gcd(a, b) = a \times b$ and use it to compute the LCM of $24$ and $36$ . Discuss its use in solving problems.

Tap card to reveal answer

Answer 20

Fundamental relationship: For any two positive integers $a$ and $b$ :
$\text{LCM}(a, b) \times \gcd(a, b) = a \times b$

Reasoning: Using prime factorizations, GCD takes the minimum exponent of each prime and LCM takes the maximum. For each prime, $\min + \max =$ sum of the two exponents, which reconstructs the product $a \times b$ .

Computing LCM of $24$ and $36$ :

First find :
- $36 = 24 \times 1 + 12$
- $24 = 12 \times 2 + 0 \Rightarrow \gcd = 12$
Apply the formula:
$\text{LCM}(24, 36) = \frac{24 \times 36}{12} = \frac{864}{12} = 72$

Verification via factorization:

$24 = 2^3 \times 3$ , $36 = 2^2 \times 3^2$
LCM $= 2^3 \times 3^2 = 72$ ✓

Use in problems:

Efficient LCM computation avoids costly factorization.
To avoid overflow, compute as $\frac{a}{\gcd(a,b)} \times b$ .
Widely used in problems on cycles, scheduling, and fractions.

Tap card to flip back

1 / 20

Unit2 Unit4

Unit 3: GCD and Primality testing - Subjective Questions

Did this save you a night before the exam?