# Solve the equation $285x \equiv 177 \pmod{924}$ using continued fraction

Solve the equation $285x \equiv 177 \pmod{924}$ using continued fraction

My attempt(using Wikipedia notion):

Continued fraction form for $\frac{924}{285}$ is $[3;4,6,1,9]=[q_1;q_2,q_3,q_4,q_5]$
$\frac{924}{285}=\frac{h_n}{k_n}$

We know that h_nk_{n-1}-h_{n-1}k_n=(-1)^n \Rightarrow$$924k_{5-1}-285h_{5-1}=(-1)^5. Thus, when we find h_{4} we'll get the equation: -285h_{4} \equiv (-1)^5 \pmod{924} \Rightarrow 285h_{4} \equiv (-1)^{4}\pmod{924} \Rightarrow 285h_{4}(-1)^{4} \equiv 1\pmod{924} \Rightarrow x=h_{4}(-1)^{4}177 is a solution, because h_{4}(-1)^{4} is 285^{-1} modulo 924, thus 285x \equiv 285*285^{-1}b \equiv b \pmod{924} Let's find h_{4}: \frac{h_1}{k_1}=\frac31 \Rightarrow h_1=3 \frac{h_2}{k_2}=3+\frac14=\frac{13}4 \Rightarrow h_2=13 Using h_n=q_nh_{n-1}+h_{n-2}: h_3=6*13+3=81 h_4=1*81+13=94 Bingo. Thus x=94*(-1)^4*175. This question is from an exam. The correct answer is x \equiv 153,461,769 \pmod{924} Did I do something wrong? how can x have multiple options(edit: how can I find all the options)? Any help would be highly appreciated! • I'd say that this is a strange formulation of the method. The standard formulation is just the extended euclidean algorithm. The long integer divisions and the quotient sequence are of course the same as the one in determining the continued fraction. – Dr. Lutz Lehmann Feb 22 '14 at 20:58 • Except that your quotient sequence is wrong. Should be [3;4,7,1,2], see answer below. – Dr. Lutz Lehmann Feb 22 '14 at 21:32 • There are 3 options, because \gcd(285,924)=3, and 3 divides 177. – Gerry Myerson Feb 22 '14 at 22:53 • Oh... I did a stupid mistake. gcd(285,924)=3 \neq 1, so I was looking at the wrong equations. I should've done the calculations on the equation 95x=59(mod308) – Eliran Koren Feb 23 '14 at 11:07 ## 1 Answer 285x≡177\pmod{924} or 285x+924y=177 can be solved using the extended euclidean algorithm for the gcd of 285 and 924. The remainder sequence of the euclidean algorithm starts with r_0=a=924, r_1=b=285 and for the extended variant the Bezout factor sequence for the Bezout identity$$v_k b≡r_k\;\pmod a\qquad (\text{short version of }u_ka+v_kb=r_k)starts with v_0=0, v_1=1 Then the algorithm proceeds iterating over k=1,2,... \begin{align} q_k&=r_{k-1}\,\text{div}\,r_k,\\ r_{k+1}&=r_{k-1}-q_kr_k, \\ v_{k+1}&=v_{k+1}-q_kv_k \end{align} resulting in the table\begin{array}{c|c|c|c|} k& q_k&r_k&v_k\\\hline 0 & & 924 & 0 \\ 1 & 3 & 285 & 1 \\ 2 & 4 & 69 & -3 \\ 3 & 7 & 9 & 13 \\ 4 & 1 & 6 & -94 \\ 5 & 2 & 3 & 107 \\ 6 & & 0 & -308 \\ \end{array}$$that is, in the end we get the gcd(285,\,924)=3 and$$107\cdot 285 ≡ 3 \pmod{924}.$Fortunately,$177=3⋅59$is divisible by$3$, so$3x≡3⋅59⋅107\pmod{3⋅308}\$ has the 3 solutions

\begin{align} x&=59⋅107\mod 308&&=153, \\ x&=153+308&&=461&&\text{ and } \\ x&=461+308&&=769.\end{align}

• One can build the table very simply using row operations, see here for a detailed explanation. – Bill Dubuque Feb 22 '14 at 23:18
• Although the question asked to solve using continued fraction, I realized my mistake, and you showed me a new method. Thanks! – Eliran Koren Feb 23 '14 at 11:10