Number Theory (Intermediate)

Question 1

(a) Irrationality of $\sqrt2$ (6)

• Assume for contradiction $\sqrt2 = a/b$ with $a,b\in\mathbb Z$, $b\neq0$, and $\gcd(a,b)=1$ (fraction in lowest terms). (1)
• Then $2b^2 = a^2$, so $a^2$ is even $\Rightarrow a$ is even (since the square of an odd number is odd). Write $a=2k$. (2)
• Then $2b^2 = 4k^2 \Rightarrow b^2 = 2k^2$, so $b^2$ is even $\Rightarrow b$ is even. (2)
• Now $2\mid a$ and $2\mid b$ contradicts $\gcd(a,b)=1$. Hence no such fraction exists: $\sqrt2$ is irrational. (1)

(b) Divisibility of $5940$ (6)

• By 4: last two digits $40$; $40 = 4\times10$, divisible by 4. ✓ (1) (rule: $100\equiv0\pmod4$ so only last two digits matter)
• By 9: digit sum $5+9+4+0=18$, and $9\mid18$. ✓ (1)
• By 11: alternating sum (from right) $0-4+9-5=0$, and $11\mid0$. ✓ (1)
• Proof of the 11-rule (3): Since $10\equiv-1\pmod{11}$, we have $10^k\equiv(-1)^k\pmod{11}$. For $N=\sum_k d_k10^k$, $N\equiv \sum_k d_k(-1)^k \pmod{11},$ which is exactly the alternating digit sum. Hence $11\mid N \iff 11$ divides the alternating sum. For $5940$: $0\cdot1+4\cdot(-1)+9\cdot1+5\cdot(-1)=0$. (3)

(c) Terminating criterion (4)

• Counterexample: $\tfrac13 = 0.\overline{3}$ is rational but non-terminating. (2)
• Criterion: a fraction $\tfrac pq$ in lowest terms has a terminating decimal expansion iff the only prime factors of $q$ are $2$ and/or $5$, i.e. $q = 2^a5^b$. (2)

Question 2

(a) $\gcd(1769,551)$ (4)

$1769 = 3\cdot551 + 116$ $551 = 4\cdot116 + 87$ $116 = 1\cdot87 + 29$ $87 = 3\cdot29 + 0$ Last nonzero remainder $\Rightarrow \gcd = 29$. (4) (1 mark per correct line, or 4 for full correct chain)

(b) Bézout coefficients (6)

Back-substitute: $29 = 116 - 1\cdot87$ $= 116 - 1\cdot(551-4\cdot116) = 5\cdot116 - 1\cdot551$ $= 5\cdot(1769-3\cdot551) - 1\cdot551 = 5\cdot1769 - 16\cdot551.$ So $x=5,\ y=-16$: $\;1769(5)+551(-16)=8845-8816=29.$ ✓ (6)

(c) CRT (8)

Moduli $3,5,7$ pairwise coprime, $M=105$. (1)

• $M_1=35,\ 35\equiv2\pmod3,\ 2^{-1}\equiv2\pmod3\Rightarrow$ term $=2\cdot35\cdot2=140$. (2)
• $M_2=21,\ 21\equiv1\pmod5,\ 1^{-1}=1\Rightarrow$ term $=3\cdot21\cdot1=63$. (2)
• $M_3=15,\ 15\equiv1\pmod7,\ 1^{-1}=1\Rightarrow$ term $=2\cdot15\cdot1=30$. (2)
• $x\equiv140+63+30=233\equiv233-105\cdot2=23\pmod{105}$. (1)

Check: $23\equiv2\ (3)$, $23\equiv3\ (5)$, $23\equiv2\ (7)$. ✓ Uniqueness: CRT guarantees a unique residue mod $M=3\cdot5\cdot7=105$ since moduli are pairwise coprime.

Answer: $x\equiv 23 \pmod{105}$.

Question 3

(a) Fermat + $3^{100}\bmod7$ (5)

• FLT: if $p$ prime and $p\nmid a$, then $a^{p-1}\equiv1\pmod p$. (1)
• Here $p=7$: $3^6\equiv1\pmod7$. (1)
• $100 = 6\cdot16 + 4$, so $3^{100}=(3^6)^{16}\cdot3^4\equiv1^{16}\cdot3^4\pmod7$. (2)
• $3^4=81\equiv81-77=4\pmod7$. Answer: $4$. (1)

(b) Rotating disk (5)

• After $n$ ticks read-out $=7n\bmod12$. Return to $0$ means $12\mid 7n$. (1)
• Since $\gcd(7,12)=1$, $12\mid 7n \Rightarrow 12\mid n$. (2)
• Smallest positive such $n = 12$. (1)
• General principle: the disk revisits $0$ after $\dfrac{12}{\gcd(7,12)} = 12$ ticks; because $7$ and $12$ are coprime, all $12$ markers are visited before repeating (the step generates the whole cyclic group $\mathbb Z_{12}$). (1)

(c) Fast exponentiation (6)

def modexp(a, e, m):
    result = 1
    a = a % m
    while e > 0:
        if e & 1:            # if lowest bit set, multiply
            result = (result * a) % m
        a = (a * a) % m      # square the base
        e >>= 1              # drop processed bit
    return result

• Correctness: uses $a^e = \prod a^{2^i}$ over set bits of $e$. (2)
• Complexity: the loop runs once per bit of $e$, i.e. $\lfloor\log_2 e\rfloor+1$ iterations, each doing $O(1)$ modular multiplications $\Rightarrow O(\log e)$ multiplications, vastly better than $O(e)$ for naive repeated multiplication. (2)
• modexp(3, 100, 7) returns 4 (consistent with part (a)). (2)

[
  {"claim":"gcd(1769,551)=29","code":"result = (gcd(1769,551)==29)"},
  {"claim":"Bezout: 1769*5 + 551*(-16) = 29","code":"result = (1769*5 + 551*(-16) == 29)"},
  {"claim":"CRT solution x=23 mod 105 satisfies all three congruences","code":"result = (23%3==2 and 23%5==3 and 23%7==2)"},
  {"claim":"3^100 mod 7 = 4","code":"result = (pow(3,100,7)==4)"},
  {"claim":"disk returns to 0 first at n=12 ticks","code":"result = (min(n for n in range(1,100) if (7*n)%12==0)==12)"}
]