Number Theory (Intermediate)

Question 1 (10 marks)

(a) Proof of the rule for 11 (6): Write $N = \sum_{k=0}^{n} d_k 10^k$ (digits $d_k$). (1) Key fact: $10 \equiv -1 \pmod{11}$, hence $10^k \equiv (-1)^k \pmod{11}$. (2) Therefore $N \equiv \sum_{k=0}^n d_k (-1)^k = d_0 - d_1 + d_2 - \cdots \pmod{11}.$ (2) So $11 \mid N \iff 11 \mid$ (alternating digit sum). Both directions follow since congruence mod 11 is an equivalence. (1)

(b) Test $918082$ (4): Digits from units up: $2,8,0,8,1,9$. Alternating sum $= 2 - 8 + 0 - 8 + 1 - 9 = -22$. (3) $-22 = -2\times 11$, divisible by 11, so $918082$ is divisible by 11. (1) (Check: $918082/11 = 83462$.)

Question 2 (10 marks)

Assume $\sqrt2$ is rational: $\sqrt2 = p/q$ with $p,q \in \mathbb{Z}$, $q\neq 0$. (2) Take the fraction in lowest terms, so $\gcd(p,q)=1$. (2) Then $2 = p^2/q^2 \Rightarrow p^2 = 2q^2$, so $p^2$ is even $\Rightarrow p$ is even (odd² is odd). Write $p=2m$. (2) Substitute: $4m^2 = 2q^2 \Rightarrow q^2 = 2m^2$, so $q^2$ even $\Rightarrow q$ even. (2) Then $2 \mid p$ and $2 \mid q$, contradicting $\gcd(p,q)=1$. Hence $\sqrt2$ is irrational. $\blacksquare$ (2)

Question 3 (12 marks)

(a) Euclidean algorithm (4): $1071 = 2\cdot 462 + 147$ $462 = 3\cdot 147 + 21$ $147 = 7\cdot 21 + 0$ So $\gcd(1071,462) = 21$. (4)

(b) Extended (6): back-substitute: $21 = 462 - 3\cdot 147$ $147 = 1071 - 2\cdot 462$ $21 = 462 - 3(1071 - 2\cdot 462) = 7\cdot 462 - 3\cdot 1071.$ (4) So $x=-3,\ y=7$: $1071(-3)+462(7) = -3213 + 3234 = 21.$ (2)

(c) Bézout (2): For any integers $a,b$ (not both 0), there exist $x,y$ with $ax+by=\gcd(a,b)$. (1) Verification: $1071(-3)+462(7)=21=\gcd$. ✓ (1)

Question 4 (10 marks)

def ext_gcd(a, b):
    if b == 0:               # base case (3)
        return (a, 1, 0)     # gcd=a, a*1 + 0*0 = a
    g, x1, y1 = ext_gcd(b, a % b)   # recurse (2)
    x = y1                          # coefficient update (2)
    y = x1 - (a // b) * y1          # (1)
    return (g, x, y)

Why correct (2): If $g = b x_1 + (a\bmod b) y_1$ and $a\bmod b = a - \lfloor a/b\rfloor b$, substituting gives $g = a\,y_1 + b(x_1 - \lfloor a/b\rfloor y_1)$, matching the returned $(x,y)$.

Question 5 (10 marks)

Moduli $3,5,7$, $M=105$; $M_1=35, M_2=21, M_3=15$. (1) Inverses:

• $35 \equiv 2 \pmod 3$, need $2y\equiv1 \Rightarrow y=2$. (2)
• $21 \equiv 1 \pmod 5$, inverse $=1$. (2)
• $15 \equiv 1 \pmod 7$, inverse $=1$. (1)

$x \equiv 2\cdot35\cdot2 + 3\cdot21\cdot1 + 2\cdot15\cdot1 = 140 + 63 + 30 = 233 \pmod{105}.$ (3) $233 \bmod 105 = 233 - 210 = 23.$ (1) Solution: $x \equiv 23 \pmod{105}$. (Check: $23=3\cdot7+2$✓, $23=4\cdot5+3$✓, $23=3\cdot7+2$✓)

Question 6 (8 marks)

(a) FLT (3): If $p$ is prime and $p \nmid a$, then $a^{p-1} \equiv 1 \pmod p$. (Equivalently $a^p \equiv a \pmod p$ for all $a$.)

(b) Compute $3^{100}\bmod 7$ (5): $p=7$, $7\nmid 3$, so $3^6 \equiv 1 \pmod 7$. (2) $100 = 6\cdot16 + 4$, so $3^{100} = (3^6)^{16}\cdot 3^4 \equiv 3^4 \pmod 7$. (2) $3^4 = 81 = 7\cdot11 + 4 \equiv 4 \pmod 7$. Answer: $4$. (1)

[
  {"claim":"918082 divisible by 11 and alt sum = -22", "code":"n=918082; alt=2-8+0-8+1-9; result=(n%11==0) and (alt==-22)"},
  {"claim":"Bezout: 1071*(-3)+462*7 = gcd(1071,462)=21", "code":"from sympy import gcd; result=(1071*(-3)+462*7==21) and (gcd(1071,462)==21)"},
  {"claim":"CRT solution 23 satisfies all three congruences", "code":"x=23; result=(x%3==2) and (x%5==3) and (x%7==2)"},
  {"claim":"3**100 mod 7 = 4", "code":"result=(pow(3,100,7)==4)"}
]