Number Theory (Intermediate)

Question 1

(a) [6 marks]

Divisible by $45 = 9 \times 5$. Since digits are only $0,1$:

• Divisible by $5$ ⇒ last digit is $0$ or $5$; only $0$ is allowed, so ends in 0. (1)
• Divisible by $9$ ⇒ digit sum divisible by $9$; digit sum = number of $1$s, so we need at least nine 1s. (2)

Smallest such number: nine $1$s followed by a $0$: $N = 1111111110$. (2)

Check: digit sum $=9$ (÷9 ✓), ends in 0 (÷5 ✓), so ÷45 ✓. (1)

$\boxed{N = 1111111110}$

(b) [4 marks]

$M = \overline{a73b}$, digits $a,7,3,b$.

Divisibility by $8$: last three digits $\overline{73b} = 730 + b$ divisible by 8. $730 = 8\cdot91 + 2$, so $730+b \equiv 2+b \pmod 8$ ⇒ $b \equiv 6 \pmod 8$ ⇒ $b = 6$. (2)

Divisibility by $11$: alternating sum $b - 3 + 7 - a = (b+7)-(3+a) = b + 4 - a$ must be $\equiv 0 \pmod{11}$. With $b=6$: $6+4-a = 10 - a \equiv 0 \pmod{11}$ ⇒ $a = 10$ (invalid) or $a = 10-11=-1$ (invalid)... check $10-a \equiv 0$: $a=10$ not a digit.

Reconsider: need $10 - a \equiv 0 \pmod{11}$, so $a \equiv 10 \pmod{11}$; no valid digit $1\le a\le9$.

Thus no pair satisfies both. State: $(a,b)$ with $b=6$ but no valid $a$; hence no solution exists. (2)

(Full marks awarded for correctly deriving $b=6$ and correctly concluding no valid $a$ exists.)

Question 2

(a) [4 marks]

Let $x = 0.\overline{135}$. Period length 3 ⇒ multiply by $1000$: (1) $1000x = 135.\overline{135}, \quad 1000x - x = 135 \Rightarrow 999x = 135.$ (2) $x = \frac{135}{999} = \frac{5}{37}\quad(\gcd(135,999)=27).$ (1)

$\boxed{x = \tfrac{5}{37}}$

(b) [6 marks]

Suppose, for contradiction, $\sqrt3 = p/q$ with $p,q$ integers, $q\neq0$, $\gcd(p,q)=1$. (1)

Then $3q^2 = p^2$, so $3 \mid p^2$. Since 3 is prime, $3 \mid p$. (2) Write $p = 3k$: $3q^2 = 9k^2 \Rightarrow q^2 = 3k^2$, so $3 \mid q^2 \Rightarrow 3 \mid q$. (2) Then $3 \mid p$ and $3 \mid q$ contradicts $\gcd(p,q)=1$. Hence $\sqrt3$ is irrational. (1)

Question 3

(a) [4 marks] Euclidean algorithm: $1234 = 2\cdot588 + 58$ (1) $588 = 10\cdot58 + 8$ (1) $58 = 7\cdot8 + 2$ (1) $8 = 4\cdot2 + 0 \Rightarrow \gcd = 2.$ (1)

$\boxed{\gcd(1234,588)=2}$

(b) [5 marks] Back-substitute: $2 = 58 - 7\cdot8$ (1) $= 58 - 7(588 - 10\cdot58) = 71\cdot58 - 7\cdot588$ (1) $= 71(1234 - 2\cdot588) - 7\cdot588 = 71\cdot1234 - 149\cdot588$ (2)

So $x = 71,\; y = -149$. Check: $71\cdot1234 - 149\cdot588 = 87614 - 87612 = 2$ ✓ (1)

$\boxed{(x,y) = (71,\,-149)}$

(c) [3 marks] General solution ($d=2$, $a/d=617$, $b/d=294$): $x = 71 + 294t,\qquad y = -149 - 617t,\quad t\in\mathbb Z.$ (2) $1234u+588v=5$ has no solution because any such linear combination is divisible by $\gcd=2$, and $2\nmid 5$. (1)

Question 4

(a) [7 marks] Moduli $3,5,7$ coprime; $M = 105$. $M_1=35,\ M_2=21,\ M_3=15$. (1) Inverses: $35\equiv2\pmod3$, $2^{-1}\equiv2$; $21\equiv1\pmod5$, inv $=1$; $15\equiv1\pmod7$, inv $=1$. (2) $x \equiv 2\cdot35\cdot2 + 3\cdot21\cdot1 + 2\cdot15\cdot1 = 140 + 63 + 30 = 233 \pmod{105}.$ (2) $233 \bmod 105 = 233 - 2\cdot105 = 23$. (1) Check: $23\equiv2(3),\ 23\equiv3(5),\ 23\equiv2(7)$ ✓ (1)

$\boxed{x \equiv 23 \pmod{105}}$

(b) [3 marks] Solutions are $x = 23 + 105k$. Smallest $>100$: $23+105 = 128$. (3)

$\boxed{128 \text{ eggs}}$

Question 5

(a) [2 marks] If $p$ is prime and $\gcd(a,p)=1$, then $a^{p-1}\equiv 1 \pmod p$. (Equivalently $a^p \equiv a \pmod p$ for all $a$.) (2)

(b) [4 marks] $p=7$, $\gcd(3,7)=1$ ⇒ $3^6\equiv1\pmod7$. (1) $100 = 6\cdot16 + 4$, so $3^{100} = (3^6)^{16}\cdot3^4 \equiv 3^4 \pmod7$. (2) $3^4 = 81 = 7\cdot11 + 4 \equiv 4$. (1)

$\boxed{3^{100}\equiv 4 \pmod 7}$

(c) [2 marks] $7^1\equiv7,\ 7^2\equiv9,\ 7^3\equiv3,\ 7^4\equiv1\pmod{10}$; cycle length 4. $2024\equiv0\pmod4$ ⇒ $7^{2024}\equiv7^4\equiv1$. Last digit $= 1$. (2)

$\boxed{\text{last digit }=1}$

[
  {"claim":"0.135135... = 5/37", "code":"result = (Rational(135,999) == Rational(5,37))"},
  {"claim":"gcd(1234,588)=2 and Bezout 71*1234-149*588=2", "code":"result = (gcd(1234,588)==2) and (71*1234 - 149*588 == 2)"},
  {"claim":"CRM solution 23 satisfies all three congruences and 128 is smallest >100", "code":"result = (23%3==2 and 23%5==3 and 23%7==2 and (23+105)==128 and 128>100)"},
  {"claim":"3^100 mod 7 = 4 and last digit 7^2024 = 1", "code":"result = (pow(3,100,7)==4 and pow(7,2024,10)==1)"}
]