# Solving $315 x \equiv 5 \pmod {11}$

I have to solve this: $$315 x \equiv 5 \pmod {11}$$

Isn't it like that?

$$315 \equiv (22+8) \cdot 10+15 \equiv 8 \cdot 3+4 \equiv 5+8+4 \equiv 6$$

Or have I done something wrong?

-
did you write $10 \equiv 3 \pmod {11}$? –  Ant May 10 '14 at 12:45
$315 = 7 \pmod {11}$, so inverting $7$ modulo $11$ gives $8$ and multiplying through $5$ and reducing gives you $x = 7 \pmod{11}$ –  Balarka Sen May 10 '14 at 12:55

First verify that $315\equiv 7\pmod{11}$. (I don't understand how you calculated $\equiv 6$). Then solve $7x\equiv 5\pmod{11}$; in this order of magintude, trial and error is good enough: Which of the numbers $5, 16, 27, 38, \ldots$ is a multiple of $7$?

-

$315\equiv 7\pmod{11}\\7x\equiv5\pmod{11}\\-4x\equiv-6\pmod{11}\\2x\equiv3\pmod{11}\\2x\equiv-8\pmod{11}\\x\equiv-4\pmod{11}\\x\equiv7\pmod{11}$

-

If we use Fermat's little theorem and the fact that $315 \equiv 7\text{ (mod 11)}$, then $7^{11 - 1}\equiv 1 \text{ (mod } 11) \implies 7^{11 - 1} \cdot 5 \equiv 5 \text{ (mod } 11) \implies 7 \cdot 7^{11-2} \cdot 5\equiv 5\text{ (mod 11)} \implies 7 \cdot 8 \cdot 5 \equiv 5 \text{ (mod 11)} \implies x \equiv 40 \text{ (mod 11)} \implies x \equiv 7 \text{ (mod 11)}.$

-

You might simplify solving $315x \equiv 5$ (mod $11$) to $63x \equiv 1$ (mod $11$) by dividing through by $5.$ Multiply by $4$ to get rid of the factor $3$ on LHS, so need to solve $21x \equiv 4$ (mod $11$), and then notice that $21 \equiv -1$ mod $11,$ so that $x \equiv -4 \equiv 7$ (mod $11$).

-