Unit6 - Subjective Questions

Definition of Divisibility:
Let and be integers with $a
eq 0aba|bkb = ak$.

Transitivity Property:
If and , then .

Proof:

1. Since , there exists an integer such that .
2. Since , there exists an integer such that .
3. Substituting the value of from step 1 into step 2:
   
   
   
4. Since and are integers, their product is also an integer.
5. Thus, , which implies .

Hence, divisibility is transitive.

We apply the Euclidean Algorithm to find :

Step 1: Euclidean Algorithm

The last non-zero remainder is 18. Thus, .

Step 2: Back Substitution (Linear Combination)
We express 18 in terms of 252 and 198 using the equations above in reverse order:

From (3):

Substitute (2) ():

Substitute (1) ():

Result:

Statement of Bezout's Lemma:
For any integers and (not both zero), there exist integers and such that:

Significance in Linear Congruences:
Bezout's Lemma is fundamental to solving linear congruences of the form .

1. Existence of Solutions: The congruence has a solution if and only if divides . This comes directly from the fact that the linear Diophantine equation is solvable only if divides .
2. Modular Inverse: Specifically, if , Bezout's Lemma guarantees integers and such that . Taking modulo , we get . This means is the modular multiplicative inverse of . Finding this inverse is crucial for cryptography algorithms like RSA and the Affine cipher.

Fundamental Theorem of Arithmetic:
Every integer can be represented as a product of prime numbers in a unique way, except for the order of the factors. That is, any integer can be written as:

Relationship between GCD and LCM:
For any two positive integers and , the product of their Greatest Common Divisor (GCD) and Least Common Multiple (LCM) equals the product of the numbers themselves:

This implies:

To solve , we need to eliminate the coefficient 4 by multiplying by its modular inverse.

Step 1: Check GCD
. Since 1 divides 5, a unique solution exists modulo 9.

Step 2: Find the modular inverse of 4 mod 9
We look for an integer such that .
Using Extended Euclidean or inspection:


Taking modulo 9:

Since , the inverse is 7.
(Check: ).

Step 3: Multiply original congruence by the inverse

Step 4: Reduce modulo 9

Answer: .

Caesar Cipher Procedure:
The Caesar cipher is a substitution cipher where each letter in the plaintext is shifted by a fixed number of positions .

• Mapping: Map letters A-Z to integers 0-25 ().
• Encryption: Let be the numerical value of a plaintext letter. The ciphertext value is calculated as:
  
• Decryption: To recover from :
  

Example: Encrypting "DATA" with :

1. D: Value $3$. . Map 6 G.
2. A: Value $0$. . Map 3 D.
3. T: Value $19$. . Map 22 W.
4. A: Value $0$. . Map 3 D.

Ciphertext: GDWD

Statement of CRT:
Let be positive integers that are pairwise relatively prime (i.e., for $i
eq j$). Then the system of congruences:




has a unique solution modulo .

Solution for the given system:
Given: ; ; .

1. Calculate :
   .

2. Calculate :
   
   
   

3. Calculate Modular Inverses such that :

4. Calculate :
   

   
   
   
   

5. Final reduction:
   

   
   

Answer:

Affine Cipher:
An affine cipher encrypts a letter using the function , where and are keys and is the size of the alphabet.

Requirement for Coprimality:
The key must be coprime to (i.e., ) so that has a multiplicative inverse modulo . If an inverse exists, the encryption function is a bijection (one-to-one mapping), allowing unique decryption. If $\gcd(a, m)
eq 1$, multiple plaintext letters map to the same ciphertext letter, making unique decryption impossible.

Finding Decryption Function:
Given .
We need to solve for : .

1. Find the inverse of .
   Using Extended Euclidean Algo: .
   .
   .
   So, .

2. Multiply the equation by :
   
   

3. Reduce constant:
   .
   So .
   .
   Or (since ).

Decryption Function: .

Fermat's Little Theorem:
If is a prime number and is an integer not divisible by (i.e., ), then:

Calculation of :
Here and . Since 11 is prime and 3 is not divisible by 11, we apply the theorem:

We express the exponent 31 in terms of 10:
.

So,

Remainder: 3

Distinction:

• Prime Number: An integer whose only positive divisors are 1 and itself (e.g., 2, 3, 5, 7).
• Composite Number: An integer that is not prime, meaning it has at least one divisor other than 1 and itself (e.g., 4, 6, 9).

Proof (Euclid's Proof of Infinite Primes):

1. Assume, for the sake of contradiction, that there are finitely many primes: .
2. Consider the integer .
3. By the Fundamental Theorem of Arithmetic, has at least one prime divisor, say .
4. If is one of the existing primes , then divides the product .
5. Since divides and divides , must divide their difference:
   
6. However, no prime number can divide 1.
7. This contradiction implies that the assumption was false. Therefore, there are infinitely many primes.

Condition for Existence:
The inverse of exists if and only if .
Check :
Since 13 is prime and does not divide 24, . The inverse exists.

Derivation using Extended Euclidean Algorithm:

Back Substitution:

Substitute (2) into above ():


Substitute (1) into above ():

Result:

Taking modulo 24:

The inverse is .
To make it positive: .

Answer: The inverse of 13 modulo 24 is 13.

Modular Arithmetic:
A system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. We write if divides .

Proof:
Let and .
By definition of division algorithm:
where
where

Now consider :

Taking modulo on both sides:

Substituting back and :

Hence proved.

Vulnerabilities of Caesar Cipher:

1. Small Key Space: The key is an integer between 1 and 25. An attacker can easily perform a Brute Force attack by trying all 25 shifts.
2. Frequency Analysis: Since it is a mono-alphabetic substitution cipher, the frequency distribution of letters in the ciphertext matches the underlying language (e.g., 'E' is the most common letter in English). An attacker can map the most frequent ciphertext letter to 'E' to find the key.

Affine Cipher Improvement:
The Affine cipher uses a linear function .

• Key Space: There are 12 possible values for (coprime to 26) and 26 values for . Total keys = . This is significantly larger than the Caesar cipher's 25 keys, making brute force slightly harder (though still trivial for computers).

Remaining Weakness:

• Still Mono-alphabetic: Like Caesar, Affine maps one plaintext letter to exactly one ciphertext letter consistently. It preserves the frequency distribution of the language, making it vulnerable to Frequency Analysis. If an attacker guesses mappings for two common letters (e.g., 'e' and 't'), they can solve the system of linear equations to find and .

We need to find such that:

Method of Substitution:
From (1), we can write:
for some integer .

Substitute this into (2):

To solve for , multiply by the inverse of 3 mod 5 (which is 2):



So, , or .

Substitute back into the expression for :

Result:
.
(Check: and . Correct.)

Formula:
The binomial coefficient is given by:

Proof:

1. Rearrange the equation:
   
2. Since is prime, it appears in the prime factorization of exactly once (as the factor itself). all other factors are less than .
3. Look at the Right Hand Side (RHS): and are products of integers all strictly less than (since ).
4. Because is prime, if divides a product , it must divide or . Since does not divide any integer less than itself, cannot divide nor .
5. Therefore, for the equation to hold, must divide .

Hence, is divisible by .

Finding the last digit is equivalent to finding .

Using Modular Arithmetic Patterns:
Powers of 7 modulo 10:




(Pattern repeats: 7, 9, 3, 1).

The cycle length is 4.

Calculation:
We need . Since the exponent 100 is a multiple of 4 ():

Answer: The last digit is 1.

Number theory is the mathematical backbone of modern cryptography, particularly Public Key Cryptography (Asymmetric Encryption).

1. Hardness of Factoring (Primes):
Systems like RSA rely on the fact that while it is easy to multiply two large prime numbers together (), it is computationally infeasible to factor the resulting large integer back into and . This asymmetry allows to be public (part of the public key) while keeping and private.

2. Modular Arithmetic & Inverses:
Encryption and decryption operations often involve modular exponentiation (). To decrypt, one needs a private key , which is the modular multiplicative inverse of the public key modulo .

• .
• The existence and calculation of this inverse (via Euclidean algorithm) ensure that the original message can be mathematically recovered (), but only by someone who knows the trapdoor information (the factors of ).

Condition for Solvability:
A linear congruence has a solution if and only if divides .

Step 1: Calculate GCD
.
.

Step 2: Check Divisibility
Does divide ? Does 3 divide 6?
Yes. Therefore, there are exactly incongruent solutions modulo 9.

Step 3: Solve
Divide the entire equation by :

Reduce coefficients mod 3:

Divide by 2 (or multiply by inverse of 2 mod 3, which is 2):
.

Step 4: Find General Solutions
The solutions are of the form for .

Step size .

Solutions:

Answer: The solutions are .

We need to show . Since , it suffices to show for each prime factor .

1. Mod 13: By Fermat's Little Theorem (FLT), . Holds.
2. Mod 7: FLT says .
   . Holds.
3. Mod 5: FLT says .
   . Holds.
4. Mod 3: FLT says .
   . Holds.
5. Mod 2: . Obviously (parity matches). Holds.

Since is divisible by all pairwise coprime factors 2, 3, 5, 7, and 13, it is divisible by their product 2730.

Definition:
Two integers and are relatively prime (or coprime) if their Greatest Common Divisor is 1, i.e., .

Proof:
Let .
By definition of GCD, divides both and .

Since divides these terms, it must divide their sum and their difference:

• Sum:
• Difference:

So, is a common divisor of and .
Therefore, divides .
.

Since we are given that and are relatively prime, .
Thus, divides , which means .

The positive divisors of 2 are 1 and 2.
Therefore, must be either 1 or 2.