Unit 6: Number Theory and Its Application in Cryptography - Subjective Questions

Definition: For integers and with , we say that divides , written , if there exists an integer such that .

Fundamental properties:

• Reflexivity: For every integer , because .
• Transitivity: If and , then . If and , then .
• Linear-combination property: If and , then for all integers .
• Product property: If , then for every integer .
• Antisymmetry up to sign: If and , then .

Example: Since and , it follows that .

For integers and a positive integer , we write

if and only if .

Equivalence relation:

• Reflexive: , and ; hence .
• Symmetric: If , then ; hence .
• Transitive: If and , then ; hence .

Compatibility properties: If and , then

• ,
• ,
• .

Therefore, congruences can be added, subtracted, and multiplied like ordinary equalities. Division is valid only when the divisor is invertible modulo .

1. Least nonnegative residue of modulo :

Since

we obtain

Thus, the least nonnegative residue is .

2. Evaluation of :

Compute successive powers:

Since ,

Therefore,

• A prime number is an integer whose only positive divisors are and .
• A composite number is an integer that has a positive divisor other than and .

Fundamental Theorem of Arithmetic: Every integer greater than is either prime or can be expressed as a product of primes. This prime factorization is unique apart from the order of the factors.

To test whether is prime, it is sufficient to test prime divisors not exceeding

The relevant primes are and . We find that

Therefore, , so is composite, not prime. Its prime factorization is

For positive integers and , the greatest common divisor and least common multiple satisfy

Using prime factorizations,

The GCD is obtained by taking the minimum exponent of each common prime:

The LCM is obtained by taking the maximum exponent of every prime:

Verification:

and

Hence,

The Euclidean algorithm is based on the fact that

The larger number is repeatedly divided by the smaller number until the remainder becomes zero. The last nonzero remainder is the GCD.

Apply the algorithm:

The last nonzero remainder is . Therefore,

The algorithm is efficient even for very large integers and is important in modular arithmetic and cryptography.

First apply the Euclidean algorithm:

Thus, .

Now substitute backward:

Since ,

Since ,

Therefore,

Hence the Bézout coefficients are and , and the required linear combination is

Bézout's lemma: For integers and , not both zero, there exist integers and such that

Proof:

• Consider the set of all positive linear combinations

• By the well-ordering principle, has a smallest element, say .
• Divide by : , where .
• Then

• Thus, is also a nonnegative linear combination of and . If , it would contradict the minimality of . Hence , so .
• Similarly, . Therefore, is a common divisor.
• Every common divisor of and divides every linear combination , so it divides .

Consequently, .

Important consequence: An integer has a multiplicative inverse modulo if and only if . If , then , so is the inverse of modulo .

A linear congruence

has a solution if and only if

If divides , then the congruence has exactly incongruent solutions modulo .

For

we have

Since , solutions exist. Divide the congruence by :

The inverse of modulo is because . Therefore,

The four incongruent solutions modulo are

Consider

First compute

Since , the congruence has exactly two incongruent solutions modulo . Divide throughout by :

The inverse of modulo is , because

Multiplying by gives

Thus,

For a complete residue system modulo , take . Hence the two solutions are

Verification:

• ,
• .

An integer has a multiplicative inverse modulo if and only if

An inverse is an integer satisfying

Apply the Euclidean algorithm:

Substitute backward:

Reducing modulo gives

Since ,

Indeed, .

Chinese Remainder Theorem: If are pairwise relatively prime positive integers, then the system

has a unique solution modulo .

Here,

Let

Find the required inverses:

• , and .
• , and .
• , and .

Therefore,

Thus,

Hence,

For two congruences

a common solution exists if and only if

or equivalently,

When a solution exists, it is unique modulo .

For the given system,

Also,

and . Therefore, the system is compatible.

Numbers congruent to modulo are

Among these, . Hence is a solution. Since

all solutions are

In a Caesar cipher, letters are represented by numbers

For a key or shift , the encryption rule is

and the decryption rule is

For :

• ,
• ,
• ,
• ,
• ,
• .

Therefore,

The encrypted ciphertext is DWWDFN. Applying a shift of to each ciphertext letter recovers the original plaintext.

The Caesar decryption formula is

Using , shift every ciphertext letter three positions backward:

• ,
• ,
• ,
• ,
• .

Thus,

Reasons the Caesar cipher is insecure:

• It has only possible shifts, or only nontrivial keys.
• An attacker can test every key using a brute-force attack.
• The cipher preserves letter-frequency patterns.
• Repeated plaintext letters produce repeated ciphertext letters.
• Common words and language patterns can easily reveal the shift.

Therefore, the Caesar cipher is useful for illustrating modular encryption but is unsuitable for modern secure communication.

The affine cipher represents letters by and encrypts each letter using

For decryption, must possess an inverse modulo . Therefore, the key is valid only if

For and , , so the key is valid.

Encrypt MATH:

• : , giving .
• : , giving .
• : , giving .
• : , giving .

Therefore,

The encryption rule is

Subtract :

The inverse of modulo is , because

Multiplying by gives the decryption function

Now decrypt QIZR:

• : , giving .
• : , giving .
• : , giving .
• : , giving .

Therefore,

Caesar cipher:

• Encryption: .
• Decryption: .
• The key is a single shift .
• There are possible keys, including the identity shift.

Affine cipher:

• Encryption: .
• Decryption: .
• The key is an ordered pair .
• The value must satisfy .
• There are choices for and choices for , giving keys.

Comparison:

• The Caesar cipher is a special affine cipher with .
• The affine cipher has a larger key space and uses both multiplication and addition.
• Affine decryption requires the modular inverse of .
• Both are monoalphabetic substitution ciphers and preserve frequency patterns.
• Although the affine cipher is stronger than the Caesar cipher, both are insecure against modern cryptanalysis.

Fermat's Little Theorem: If is prime and , then

An equivalent form, valid for every integer , is

Proof:

Consider the nonzero residues

Since , multiplication by permutes these residues modulo . Therefore,

are congruent in some order to

Multiplying all corresponding residues gives

Since none of is divisible by , we have

Thus, can be cancelled modulo , giving

Multiplying by yields . If , the latter congruence also holds because both sides are congruent to zero.

Since is prime and , Fermat's Little Theorem gives

Write

Therefore,

Now,

Hence,

Finding inverses: For a prime and ,

Thus,

so

For example, modulo ,

because .