# Solve the congruence $59x\equiv 3\pmod {78}$

The question is: Solve the congruence $59x\equiv 3\pmod {78}$ So I already found the inverse of $59\pmod{78}$ which is $41$. So $41 \cdot 59\equiv 1\pmod {78}$

The solution is:

$59x\equiv 3\pmod {78}$ multiplied by inverse is

$41 \cdot 59x\equiv 41 \cdot 3\pmod {78}$

$x\equiv 123\pmod {78}$

$x\equiv 45\pmod {78}$

$x = 45$

So I have trouble understanding two parts. One, how did we get $x\equiv 123\pmod {78}$?

Two, in the part where we get $x\equiv 45\pmod {78}$ from $x\equiv 123\pmod {78}$ why is $45\pmod {78}=123\pmod {78}$? I get that $45$ is the remainder when $123$ is divided by $78$, but I don't understand how that makes it so $45\pmod {78}=123\pmod {78}$.

-
I get that part hehe, what I dont get is why $41.59x \Rightarrow x$ –  user60334 Apr 11 '13 at 3:07
Ah! Sorry. Well that's modular arithmetic: $\mathbb{Z}_{78}$ is a commutative ring. Where $41\cdot 59=1$. But if you prefer, write $41\cdot 59=1+78k$. Then $41\cdot 59 x-x=(1+78k)x-x=78kx$ is divisible by $78$. That is $41\cdot 59 x-x\equiv 0$ mod $78$, or $41\cdot 59 x\equiv x$ mod $78$. –  1015 Apr 11 '13 at 3:15

$(1)$ We get $x\equiv 123$ by multiplying $3 \cdot 41$.

$(2)$ $123 - 78 = 45$: that is, $78\mid (123 - 45)$ which means $x\equiv 123 \equiv 45 \pmod {78}$

-
oohh, similar answers at the same time, but with a different itemizing scheme. Let's see which listing method is preferred! –  mixedmath Apr 11 '13 at 3:05
@mixedmath hehehehehehe! –  amWhy Apr 11 '13 at 3:07
What I dont get in part (1) is how $41.59x \Rightarrow x$ –  user60334 Apr 11 '13 at 3:09
That's the definition of multiplicative inverse at play: $41 \cdot 59 \equiv 1 \pmod{78}.\;$ So $41\cdot 59 x \equiv 1\cdot x \equiv x \pmod {78}$. –  amWhy Apr 11 '13 at 3:12
The multiplicative inverse of a number, $\pmod n$ works in modular equivalences like the multiplicative inverse in solving a "regular old" equation: $4x = 16 \iff \dfrac{1}{4}(4x) = \dfrac 14(16) \iff x = 4$, where in the "regular old" equation example, 1/4 is the multiplicative inverse of $4$. If $k$ is the number, and $k^{-1}$ is the multiplicative inverse of $k \pmod n,$ then by definition, $k \cdot k^{-1} = 1 \pmod n$. –  amWhy Apr 11 '13 at 3:16
1. $41 \cdot 3 = 123$

2. $123 - 78 = 45$, so that in particular $78$ divides $123 - 45$. This is the definition of modular equivalence.

-