Number Theory Problems: GCD, Congruences, and Fermat Numbers

1. Find the GCD of (143, 227)

The Euclidean Algorithm is used to find the Greatest Common Divisor (GCD) of two integers by repeatedly dividing the larger number by the smaller number until the remainder becomes 0.

• Step 1: 227 = 143 × 1 + 84
• Step 2: 143 = 84 × 1 + 59
• Step 3: 84 = 59 × 1 + 25
• Step 4: 59 = 25 × 2 + 9
• Step 5: 25 = 9 × 2 + 7
• Step 6: 9 = 7 × 1 + 2
• Step 7: 7 = 2 × 3 + 1
• Step 8: 2 = 1 × 2 + 0

Since the remainder becomes 0, the last non-zero remainder is 1.

Answer: GCD(143, 227) = 1

2. Find m and n such that gcd(a, b) = ma + nb for a = 56 and b = 72

Given:

a = 56, b = 72. We need to find integers m and n such that: gcd(56, 72) = 56m + 72n.

Step 1: Find the GCD using the Euclidean Algorithm

72 = 56 × 1 + 16
56 = 16 × 3 + 8
16 = 8 × 2 + 0
Hence, gcd(56, 72) = 8.

Step 2: Express the GCD as a Linear Combination

8 = 56 - 16 × 3
Since 16 = 72 - 56, substitute this into the equation:
8 = 56 - 3(72 - 56)
8 = 56 - 3 × 72 + 3 × 56
8 = 4 × 56 - 3 × 72

Result: m = 4, n = -3

Verification: 4(56) + (-3)(72) = 224 - 216 = 8.

3. Solve the linear congruence 4x ≡ 8 (mod 24)

Step 1: Find the GCD

gcd(4, 24) = 4. Since 4 divides 8, the congruence has 4 solutions.

Step 2: Divide by the GCD

Divide the entire congruence by 4: x ≡ 2 (mod 6).

Step 3: Find the Solutions Modulo 24

The solutions are x = 2 + 6k for k = 0, 1, 2, 3:

• k = 0: x = 2
• k = 1: x = 8
• k = 2: x = 14
• k = 3: x = 20

Final Answer: x ≡ 2, 8, 14, 20 (mod 24)

4. Find the inverse of 33 modulo 91

Step 1: Check if the inverse exists

91 = 33 × 2 + 25
33 = 25 × 1 + 8
25 = 8 × 3 + 1
gcd(33, 91) = 1, so the inverse exists.

Step 2: Apply the Extended Euclidean Algorithm

1 = 25 - 3 × 8
1 = 25 - 3(33 - 25) = 4 × 25 - 3 × 33
1 = 4(91 - 2 × 33) - 3 × 33 = 4 × 91 - 11 × 33
Thus, 33(-11) ≡ 1 (mod 91). Since -11 ≡ 80 (mod 91), the inverse is 80.

5. Solve the system of simultaneous congruences

x ≡ 1 (mod 4), x ≡ 0 (mod 3), x ≡ 5 (mod 7). Using the Chinese Remainder Theorem (CRT):

• M = 4 × 3 × 7 = 84
• M1 = 21, M2 = 28, M3 = 12
• Inverses: y1 = 1, y2 = 1, y3 = 3
• x = (1)(21)(1) + (0)(28)(1) + (5)(12)(3) = 21 + 0 + 180 = 201
• 201 mod 84 = 33

Final Answer: x ≡ 33 (mod 84)

6. Fermat Numbers and Primality

Definition

A Fermat number is of the form F_n = 2²ⁿ + 1.

Proof that F₅ is divisible by 641

641 = 5 × 2⁷ + 1, so 5 × 2⁷ ≡ -1 (mod 641).
Raising to the 4th power: 5⁴ × 2²⁸ ≡ 1 (mod 641).
Since 5⁴ = 625 ≡ -16 (mod 641), we have -16 × 2²⁸ ≡ 1 (mod 641), which simplifies to 2³² ≡ -1 (mod 641).
Therefore, 2³² + 1 ≡ 0 (mod 641), meaning 641 divides F₅. Thus, F₅ is not prime.