-1

I had a test on modular arithmetic. One of the questions was

Find x such that $$ x * 11 = 5 \mod 64$$ or determine that there is no such solution.

How can I solve such an equation? I know from calculations in calc that the solution is

$$ x = 175$$

However how can I solve this in a smart way?

CuriousIndeed
  • 439
  • 2
  • 16
  • Find the multiplicative inverse of $11$ mod $64$ and multiply by $5$ – Brendan Sullivan Jul 09 '21 at 06:40
  • 2
    "*the solution is* $x=175$" $-$ That's just one solution out the family of solutions $\,47 + 64\,k\,$. – dxiv Jul 09 '21 at 06:43
  • 1
    see [this](https://math.stackexchange.com/questions/3488324/general-solution-of-a-linear-congruence-ax-equiv-b-pmod-m). – user2661923 Jul 09 '21 at 07:10
  • 1
    **Or** we can use [Newton's method (Hensel's Lemma)](https://math.stackexchange.com/a/13190/242) to lift an easy inverse mod $8$ to mod $8^2$ $$\color{#0a0}{3}^{-1}\equiv \color{#c00}3\pmod{\!8}\,\Rightarrow\, \bmod 8^2\!:\ \dfrac{5}{\color{#0a0}3\!+\!8} \overset{\large \times\ \color{#c00}3_{\phantom{|}}}= \dfrac{15}{1+4(8)} = 15(1\!-\!4(8)) = 15\!-\!(-4)8 = 47$$ – Bill Dubuque Jul 09 '21 at 07:43

2 Answers2

1

Here's the general approach. Using the Extended Euclidean Algorithm with $64$ and $11$, you find that $$11\cdot (-29)+64\cdot 5=1.$$ Thus $$11\cdot (-29)\equiv1\mod 64.$$ Coming back to your equation, we may multiply both sides by $-29$ to get $$x\cdot 1\equiv -145\mod 64.$$ As $$-145\equiv 47\mod 64,$$ we conclude that $x\in\{47+64k\mid k\in\mathbb Z\}$.

Zuy
  • 4,045
  • 1
  • 7
  • 17
0

There's probably a better way of doing this, but this was my approach.

$11x \equiv 5 \pmod{64}$ implies that there exists some integer $a$ such that $11x = 64a + 5.$ Because of this we must have $64a \equiv -2a \equiv -5 \pmod{11} \Leftrightarrow a \equiv 8 \pmod{11}.$ Letting $a = 8$ gives us $11x = 64(8) + 5 = 517 = 47\cdot11.$ So, any $x \equiv 47 \pmod{64}$ will work. (and $x = 175$ is in this class because $175 = 2(64) + 47$)

Edit: I realized this is actually a bit circular since I relied on the solution to $2a \equiv 5 \pmod{11}$ but I think this division is pretty trivial since $16 = 5 + 11 = 2\cdot8.$ In any case you could repeat the process to solve this equation: $2a = 5 + 11b \Leftrightarrow b \equiv 1 \pmod{2}, 2a = 5+11 \Leftrightarrow a = 8.$

Stephen Donovan
  • 5,158
  • 1
  • 9
  • 24
  • Please strive not to add more dupe answers to dupes of FAQs, cf. recent site policy announcement [here](https://math.meta.stackexchange.com/q/33508/242). – Bill Dubuque Jul 09 '21 at 07:21