Introduction to Number Theory

Euler’s Theorem asserts that for any integer aaa that is coprime to a positive integer mmm, the remainder when  is divided by m is 1. The reason we emphasize proving Euler’s Theorem is that Fermat’s Theorem is, in fact, a special case of it. This connection arises because when p is a prime number,  which makes Fermat’s Theorem a subset of Euler’s Theorem under these circumstances.

Euler’s Theorem is a crucial result in number theory, named after the Swiss mathematician Leonhard Euler. It reveals an important relationship between number-theoretic functions and modular arithmetic concepts. In this article, we will explore Euler’s Theorem, including its statement and proof.

Proof of Euler’s Theorem

For some a_i in {a₁, . . . , a_k}
Since this is the same set of numbers mod n as the original system, the two systems must have the same product mod n:

Now each a_i is invertible mod n, so multiplying both sides by   

Euler’s Theorem Formula

The statement of Euler’s Theorem can also serve as a formula for further calculations:

Where:

• a is any integer coprime to n
• n is a positive integer
• ϕ(n) is Euler’s totient function
• ≡ denotes equivalence
• mod n represents congruence modulo n

Example Showing Euler’s Theorem Formula

Problem: Verify Euler’s Theorem for a = 3 and n = 8.

Solution:

First, we calculate ϕ(8). The numbers less than 8 that are coprime to 8 are 1, 3, 5, and 7. Thus, ϕ(8)=4.
Next, calculate 3⁴ and find its remainder when divided by 8
3⁴ = 81
Now, find 81 mod 8
81 mod 8 ≡ 1
Thus, 3⁴ ≡ 1 (mod 8), which verifies Euler’s Theorem.

Applications of Euler’s Theorem

Euler’s Theorem has numerous applications across mathematics and other fields. Some notable uses include:

• RSA Encryption: Euler’s theorem is a cornerstone of modern cryptography, especially the RSA encryption algorithm. RSA involves generating public and private keys such that they are modular inverses modulo , where is the product of two large prime numbers.
• Problem Solving in Number Theory: Euler’s theorem is invaluable in solving number theory problems related to divisibility, remainders, and number properties in various systems.
• Primality Testing: Euler’s theorem is employed in primality testing algorithms, such as the Fermat primality test. Although this test can produce false positives for Carmichael numbers, it provides a quick way to identify non-prime numbers. If , then is not prime.
• Mathematical Proofs: Euler’s theorem serves as a general case for proofs involving modular arithmetic, divisibility tests, and number theory identities. It offers a robust foundation for rigorous mathematical arguments.

Euler’s Theorem Examples

Example 1: Find the remainder when 5¹⁰⁰ divided by 7.

Solution:

Since 7 is a prime number, ϕ(7) = 7−1 = 6

According to Euler’s can be rewritten as 

Now,

Using modular exponentiation:

Simplify 

So, when 5¹⁰⁰  is divided by 7, the remainder is 2.

We are given two arrays num[0..k-1] and rem[0..k-1]. In the array num[0..k-1], every pair of numbers is coprime (i.e., the greatest common divisor for each pair is 1). Our task is to find the smallest positive integer x such that:

x % num[0] = rem[0],
x % num[1] = rem[1],
...
x % num[k-1] = rem[k-1].

In essence, we are provided with k numbers, all of which are pairwise coprime, along with the remainders when an unknown number x is divided by these numbers. We need to determine the minimum possible value of x that satisfies all the given conditions.

Example 1:

• Input:
  num[] = {5, 7},
  rem[] = {1, 3}
• Output:
  31
  Explanation: 31 is the smallest number such that:
  • When divided by 5, the remainder is 1.
  • When divided by 7, the remainder is 3.

Example 2:

• Input:
  num[] = {3, 4, 5},
  rem[] = {2, 3, 1}
• Output:
  11
  Explanation: 11 is the smallest number such that:
  • When divided by 3, the remainder is 2.
  • When divided by 4, the remainder is 3.
  • When divided by 5, the remainder is 1.

RC4 is a stream cipher and a variable-length key encryption algorithm. It encrypts data one byte at a time (or sometimes in larger units). Using a pseudorandom bit generator, it produces an 8-bit key stream that is unpredictable without the input key. This key stream is combined with the plaintext one byte at a time using the XOR operation.

Example:

• RC4 Encryption:
  10011000 XOR 01010000 = 11001000
• RC4 Decryption:
  11001000 XOR 01010000 = 10011000

Chinese Remainder Theorem:

The Chinese Remainder Theorem guarantees that a solution always exists for this system of congruences. The first part of the theorem ensures that a solution exists, and the second part states that all solutions will produce the same remainder when divided by the product of num[0], num[1], ... , num[k-1]. For example, in the above case, the product of 3, 4, and 5 is 60, and 11 is one solution. Other solutions are of the form 11 + m*60 where m >= 0.

A naive approach to solve this problem is to start with 1 and increment it one by one, checking if dividing it by the numbers in num[] produces the corresponding remainders in rem[]. Once we find such an x, we return it. Below is the implementation using this approach.

Futheremore, all solutions of x of this system are congruent modulo the product, 

Python Code (Naive Approach):

# A Python3 program to demonstrate
# working of Chinese Remainder Theorem

# k is size of num[] and rem[].
# Returns the smallest number x
# such that:
# x % num[0] = rem[0],
# x % num[1] = rem[1],
# ..................
# x % num[k-2] = rem[k-1]
# Assumption: Numbers in num[]
# are pairwise coprime (gcd for
# every pair is 1)
def findMinX(num, rem, k):
    x = 1  # Initialize result

    # As per the Chinese remainder
    # theorem, this loop will
    # always break.
    while True:

        # Check if remainder of
        # x % num[j] is rem[j]
        # or not (for all j from
        # 0 to k-1)
        j = 0
        while j < k:
            if x % num[j] != rem[j]:
                break
            j += 1

        # If all remainders
        # matched, we found x
        if j == k:
            return x

        # Else try next number
        x += 1

# Driver Code
num = [3, 4, 5]
rem = [2, 3, 1]
k = len(num)
print("x is", findMinX(num, rem, k))

Output:

x is 11

Once the vector S is initialized, the input key is no longer used. The algorithm continues by cyclically permuting S and generating a key stream byte k.

x % num[0] = rem[0],
x % num[1] = rem[1],
...
x % num[k-1] = rem[k-1].

Encrypt Using XOR:
RC4 encrypts plaintext by XORing it with the generated key stream.

News on RC4

In September 2015, Microsoft announced the discontinuation of RC4 support in Microsoft Edge and Internet Explorer 11.

Features of the RC4 Algorithm

• Symmetric key encryption: RC4 uses the same key for encryption and decryption.
• Stream cipher: It encrypts and decrypts data byte by byte, generating a pseudorandom key stream XORed with the plaintext to produce ciphertext.
• Flexible key size: RC4 supports key sizes from 40 to 2048 bits, making it adaptable to varying security needs.
• High speed: It is a fast algorithm, ideal for applications requiring rapid data encryption.
• Extensive usage: Historically, RC4 was used in wireless networks, SSL, VPNs, and file encryption.
• Vulnerabilities: Known issues, such as biases in the initial key stream, make it unsuitable for new applications.

Advantages of RC4

• Efficiency: RC4 is highly efficient and suitable for use in low-power devices or scenarios requiring quick encryption.
• Simplicity: The algorithm’s design is straightforward, enabling easy implementation in both software and hardware.
• Adaptable key size: RC4’s variable key size allows it to meet diverse security requirements.
• Historical adoption: It was widely used in applications such as SSL, VPNs, and file encryption.

Disadvantages of RC4

• Vulnerabilities: Known weaknesses, including key stream biases, make RC4 susceptible to key recovery attacks.
• Security limitations: Its design has inherent flaws, making it less secure compared to modern algorithms like AES or ChaCha20.
• Restricted key length: The maximum key length of 2048 bits may not suffice for applications requiring stronger encryption.
• Deprecated usage: Due to its vulnerabilities, RC4 is no longer recommended for new implementations. Modern stream ciphers such as AES-CTR or ChaCha20 are preferred.