Unit 2: Number Theory-II - Subjective Questions

Prime Number: An integer is called a prime number if its only positive divisors are and itself.

• Examples:

Composite Number: An integer that is not prime is called composite. It has at least one divisor other than and itself.

• Examples:

Why is neither:

• The number has only one positive divisor (itself), so it does not meet the definition of a prime (which requires exactly two distinct divisors).
• It is not composite because it cannot be written as a product of smaller positive integers greater than .
• Excluding also preserves the uniqueness in the Fundamental Theorem of Arithmetic; otherwise factorizations like would not be unique.

Statement: Every integer can be expressed as a product of primes, and this factorization is unique up to the order of the factors.

Formally, any integer can be written as:

where are distinct primes and are positive integers. This representation is called the canonical prime factorization.

Two parts:

• Existence: Every integer greater than has at least one prime factorization.
• Uniqueness: There is essentially only one such factorization (order aside).

Example:

No other combination of primes multiplies to give . This uniqueness is central to number theory and cryptography.

Trial Division Method:

• To test whether an integer is prime, divide by every integer (or every prime) from up to .
• If none of these divides evenly, then is prime.
• If any divides evenly, then is composite.

Why check only up to :

• Suppose is composite, so where .
• If both and , then , a contradiction.
• Therefore at least one factor must be .
• Hence, if no divisor exists up to , the number has no non-trivial factors and is prime.

Example: To test : . Check divisibility by . None divides , so is prime.

Sieve of Eratosthenes: An efficient algorithm to find all prime numbers up to a limit .

Steps:

1. Write all integers from to .
2. Start with the first unmarked number (it is prime).
3. Mark all multiples of (i.e., ) as composite.
4. Move to the next unmarked number and repeat.
5. Continue until .
6. All remaining unmarked numbers are prime.

Demonstration for :

• Multiples of : → marked.
• Multiples of : → marked.
• Multiples of : → marked.
• Since , we stop after .

Primes up to 30:

The algorithm is efficient with time complexity .

Prime Number Theorem (PNT): Let denote the number of primes less than or equal to . Then:

This means:

Interpretation:

• The number of primes up to is approximately for large .
• Equivalently, the probability that a randomly chosen integer near is prime is about .

Significance:

• It describes how primes thin out (become less frequent) as numbers grow larger.
• It is fundamental to cryptography, where we estimate how many primes exist of a given bit-length to generate large random primes for RSA keys.

Example: For , , while , a reasonable approximation that improves for larger .

GCD: The greatest common divisor of two integers and (not both zero), denoted , is the largest positive integer that divides both and .

LCM: The least common multiple, denoted , is the smallest positive integer that is a multiple of both and .

Relationship:

Proof (using prime factorization):

• Let and over the same set of primes.
• Then:
  
• Multiplying:
  
  since .

Example: : , ;

Euclidean Algorithm: A method to find the GCD of two integers based on the principle:

repeated until the remainder becomes . The last non-zero remainder is the GCD.

Steps: Given :

1. Compute where .
2. Replace with .
3. Repeat until .
4. The last non-zero remainder is .

Computing :

The last non-zero remainder is .

The algorithm is very efficient, running in division steps.

Bézout's Identity: For any two integers and (not both zero), there exist integers and such that:

The integers and are called Bézout coefficients.

Method: Use the Extended Euclidean Algorithm by back-substituting the equations from the standard Euclidean algorithm.

Example — Express :

Forward steps:

Back-substitution:

Substitute :

Result:

So .

Role in the Fundamental Theorem of Arithmetic:

• Primes are the atomic units — every integer is either prime or a unique product of primes.
• Composites are the numbers that decompose into these prime building blocks.
• This decomposition is the essence of the FTA and underpins much of number theory and cryptography.

Theorem: There are infinitely many prime numbers.

Proof (by contradiction — Euclid's method):

1. Assume, for contradiction, that there are only finitely many primes:
   

2. Construct the number:
   

3. Now , so by the Fundamental Theorem of Arithmetic, must have at least one prime factor .

4. This prime must be one of (since these are assumed to be all the primes).

5. But dividing by any leaves a remainder of :
   
   So none of divides .

6. This contradicts the fact that has a prime factor among them.

Conclusion: Our assumption is false. Therefore, there are infinitely many primes.

Prime Factorization of :

Therefore:

Number of Positive Divisors:

If , the number of positive divisors is:

For :

So has positive divisors.

Method using Prime Factorization:

Given and :

• GCD: Take the minimum exponent for each common prime:
  
• LCM: Take the maximum exponent for each prime:
  

Computation:

Factorize:

GCD (minimum exponents):

LCM (maximum exponents):

Verification:

Relatively Prime (Coprime): Two integers and are said to be relatively prime (or coprime) if their greatest common divisor is :

This means they share no common prime factors.

Examples:

• and are coprime: , ; .
• and are not coprime: .

Importance in Cryptography:

• In the RSA algorithm, the public exponent must be chosen so that it is coprime to (Euler's totient of the modulus). This ensures has a modular multiplicative inverse satisfying .
• The existence of this inverse (guaranteed by Bézout's identity when ) is what allows decryption to reverse encryption.

Example: If , choosing works since , and its inverse satisfies .

Extended Euclidean Algorithm: An extension of the Euclidean algorithm that, along with computing , also finds integers and such that:

When , the coefficient gives the modular inverse of modulo , i.e., .

Finding inverse of mod :

Apply Euclidean algorithm:

So → inverse exists.

Back-substitution:

Thus .

Convert to positive: .

Result: The inverse of modulo is (check: ).

Comparison:

Discussion:

• Trial division is simple and memory-efficient, ideal when you need to check just one number for primality, but becomes slow for very large numbers.
• The Sieve is highly efficient when you need all primes in a range because it avoids redundant divisions by systematically eliminating multiples.
• For cryptographic-sized primes (hundreds of digits), neither is practical; probabilistic tests like Miller-Rabin are used instead.

Lemma: If , , , are integers such that , then:

Proof: We show that the set of common divisors of equals the set of common divisors of .

Part 1: Every common divisor of and divides .

• Let and .
• Since , and divides both and (because ), it follows that:
  
• So is a common divisor of and .

Part 2: Every common divisor of and divides .

• Let and .
• Since , and divides both and , it follows that:
  
• So is a common divisor of and .

Conclusion: The pairs and have exactly the same set of common divisors, hence the same greatest common divisor:

This lemma justifies repeatedly replacing with in the Euclidean algorithm.

Euclid's Lemma: If a prime divides the product of two integers, then divides at least one of them:

Why it holds:

• Suppose but .
• Since is prime and does not divide , we have .
• By Bézout's identity, there exist integers with .
• Multiply by : .
• Since and (so ), it follows .

Role in FTA Uniqueness:

• Suppose an integer has two prime factorizations:
  
• Since , by Euclid's Lemma (applied repeatedly), must divide some .
• As is prime, . Cancel them and repeat.
• This process matches each prime on one side with an equal prime on the other, proving the two factorizations are identical (up to order).

Thus Euclid's Lemma is the crucial tool guaranteeing uniqueness of prime factorization.

Step 1 — Euclidean Algorithm:

The last non-zero remainder is , so:

Step 2 — Back-substitution (Linear Combination):

From the third equation:

Substitute :

Substitute :

Result:

Here the Bézout coefficients are and .

Verification: ✓

Significance of Large Primes in Cryptography:

Modern public-key cryptosystems, especially RSA, rely heavily on the properties of large prime numbers.

Key Points:

• Key Generation: RSA generates two large random primes and (typically 1024–2048 bits each) and computes the modulus .
• Prime Number Theorem's Role: The PNT assures us that primes are abundant enough ( density) that randomly testing numbers of the required size will find primes efficiently.
• One-way Difficulty (Integer Factorization Problem):
  • Multiplying to get is easy (fast).
  • Recovering and from (factorization) is computationally infeasible for large with current algorithms.
  • This asymmetry is the trapdoor on which RSA security rests.
• Primality Testing: Efficient probabilistic tests (e.g., Miller-Rabin) allow quick verification that generated numbers are prime.

Why factorization is hard:

• No known polynomial-time classical algorithm factors large integers.
• The best-known algorithms (e.g., General Number Field Sieve) run in sub-exponential time, making sufficiently large keys secure.

Conclusion: The combination of easy prime generation and hard factorization makes large primes the cornerstone of secure communication.

Condition for Solvability: The linear Diophantine equation has integer solutions if and only if .

Given: .

Step 1 — Check Solvability:

Since divides , solutions exist.

Step 2 — Find a Particular Solution:

Express as a linear combination:

Multiply through by :

So a particular solution is .

Step 3 — General Solution:

The general solution is:


for any integer .

Result:

Verification (t=1): ✓