Solve for $C$ when $C>2018$:

Question

I am stuck on the following question:

Solve for minimum value of $C$ when $C>2018$:

$$27C\equiv 175\mod 256$$

I have been given this high school problem but I don't know what criterion to use to find a solution of this problem.

Since $(27,256)=1,\;$ I know that this congruence has a solution but I don't know how to solve it.

Any help will be appreciated.

Answer 1

$$175\equiv -81\pmod{256}$$ So we have $$27C\equiv -81\pmod{256}$$Divide both sides by $27$ we have$$C\equiv-3\pmod{256}$$

Answer 2

Guide:

\begin{align} 256 &= 27(9) + 13\\ 27 &= 2(13) + 1 \end{align} \begin{align} 1 &= 27 - 2(13)\\ &= 27 -2(256-27(9)) \\ &= 19(27) - 2(256) \end{align}

Hopefully you can see $27^{-1} \pmod{256}$ from here and take it from here.

Answer 3

Hint:

$\implies27C\equiv175\pmod8$

$\iff3C\equiv-1\pmod8\equiv-1-8$

$\iff C\equiv-3\pmod8$

If $C=8a-3,27C-175=27(8a-3)-175=216a-256$

Take $\pmod{256}\implies256|216a\iff32|27a\implies32|a$ as $(32,27)=1$

Answer 4

Hint: The extended Euclidean algorithm establishes from $(27,256)=1$ the equation $1 = a\cdot 27+b \cdot 256$ for some integers $a,b$. Then $a$ is the inverse of 27 modulo 256. Then $c \equiv 27^{-1} \cdot 175 \mod 256$.

The Maple command ''modp'' gives $a=19$.

Answer 5

$27C\equiv 175\mod 256 \iff 27C-256Y=175$

$(27,256)=1$. So, $$256=27.9+13$$ $$27=2.13+1$$ $$\begin{align} 1 &= 27 - 2.13\\ &= 27 -2(256-27.9) \\ &= 19.27 - 2.256 \end{align}$$ Multiplying $175$, $$175=175.19.27-175.2.256\iff C=175.19=3325$$

Another approximation: $$27C\equiv 175\mod 256 \iff 27C-256y=175$$ $$ \iff -256y\equiv -13y\equiv 175\equiv 13 \mod 27$$ $$\iff -13y-27z=13$$ $$ \iff -27z\equiv -z\equiv 13\mod 13$$ $$z\equiv 0 \mod 13$$ Take $z=13$, find $x$.

Answer 6

Note that $256-175=81$. Thus $27C\equiv175$ mod $256$ becomes $27C\equiv-81$ mod $256$. We can now cancel the $27$, leaving $C\equiv-3$ mod $256$. Finally, $256\times8=2048$, so $C=2045$ is the smallest value of $C\gt2018$ that satisfies the congruence.

Remark: The key thing that makes life simple here is the opening coincidence that $256-175=81=27\times3$. If the numbers had been different, the route to an answer would necessarily be different.