Maths Olympiad Prep

Library / /16 of 53

Number theory Difficulty 6.1 National olympiad Prove it Vietnam

Find the number of ordered 6-tuples satisfying the following system of modular equations
{ab+ab1(mod15)bc+bc1(mod15)ca+ca1(mod15) \begin{cases} ab + a'b' \equiv 1 \pmod{15} \\ bc + b'c' \equiv 1 \pmod{15} \\ ca + c'a' \equiv 1 \pmod{15} \end{cases}
with a,b,c,a,b,c{0,1,,14}a, b, c, a', b', c' \in \{0, 1, \dots, 14\}.

Solution

For any integer kk, let NkN_k be the number of ordered 6-tuple (a,b,c,a,b,c)(a, b, c, a', b', c') that satisfy
ab+abbc+bcca+ca1(modk) ab + a'b' \equiv bc + b'c' \equiv ca + c'a' \equiv 1 \pmod{k}
and a,b,c,a,b,c{0,1,,k1}a, b, c, a', b', c' \in \{0, 1, \dots, k-1\}. By the Chinese Remainder Theorem,
Nmn=Nn×Nm if gcd(n,m)=1. N_{mn} = N_n \times N_m \text{ if } \gcd(n, m) = 1.
Therefore, in order to compute N15N_{15}, we only need to compute N3N_3 and N5N_5. We will compute NpN_p for any pp prime. Fix a solution (a,b,a,b)(a, b, a', b') of the equation ab+ab1(modp)ab + a'b' \equiv 1 \pmod{p}, we compute the number of solutions of the following system
bc+bcca+ca1(modp)(1) bc + b'c' \equiv ca + c'a' \equiv 1 \pmod{p} \quad (1)
We consider three cases

* Suppose that (a,a)t(b,b)(modp)(a, a') \neq t(b, b') \pmod{p} for any t{0,1,,p1}t \in \{0, 1, \dots, p-1\}. Then the system (1) has a unique solution
cababba,cababba(modp) c \equiv \frac{a' - b'}{a'b - b'a}, \quad c' \equiv \frac{a - b}{ab' - ba'} \pmod{p}
* Suppose that (a,a)t(b,b)(modp)(a, a') \equiv t(b, b') \pmod{p} for some t1t \neq 1. Then the system (1) has no solution.
* Suppose that (a,a)(b,b)(modp)(a, a') \equiv (b, b') \pmod{p}. Then the system (1) becomes a single equation bc+bc1(modp)bc + b'c' \equiv 1 \pmod{p}. Since ba+ba1(modp)ba + b'a' \equiv 1 \pmod{p}, we can assume that b0b \neq 0. Hence, for any choice of cc', we have only one choice of c(1bc)/b(modp)c \equiv (1 - b'c')/b \pmod{p}. This implies that the system (1) has exactly pp solutions.

Let TpT_p be the number of ordered tuples (a,b,a,b)(a, b, a', b') that satisfy ab+ab1(modp)ab + a'b' \equiv 1 \pmod{p} and a,b,a,b{0,1,,p1}a, b, a', b' \in \{0, 1, \dots, p-1\}. For any pair (a,a)(0,0)(a, a') \neq (0, 0), there are exactly pp pairs (b,b)(b, b') satisfy the equation. Hence, Tp=p(p21)T_p = p(p^2 - 1).

Let Cp(t)C_p(t) be the number of ordered pairs (a,b)(a, b) that satisfy a2+b2t(modp)a^2 + b^2 \equiv t \pmod{p} and a,b{0,1,,p1}a, b \in \{0, 1, \dots, p-1\}. From the above arguments, we have
Np=Tpt=1p1Cp(t)+pCp(1)=p(p21)p2+Cp(0)+pCp(1). N_p = T_p - \sum_{t=1}^{p-1} C_p(t) + pC_p(1) = p(p^2 - 1) - p^2 + C_p(0) + pC_p(1).
It is easy to get C3(0)=1,C3(1)=4,C5(0)=9,C5(1)=4C_3(0) = 1, C_3(1) = 4, C_5(0) = 9, C_5(1) = 4, which implies that N3=28,N5=124N_3 = 28, N_5 = 124 and N15=28×124=3472N_{15} = 28 \times 124 = 3472.

Therefore, the number of ordered 6-tuple satisfying the given conditions is 3472. ☐

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.