# 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$ Apr 11, 2013 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$. Apr 11, 2013 at 3:15

## 3 Answers

$(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! Apr 11, 2013 at 3:05
• @mixedmath hehehehehehe! Apr 11, 2013 at 3:07
• What I dont get in part (1) is how $41.59x \Rightarrow x$ Apr 11, 2013 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}$. Apr 11, 2013 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$. Apr 11, 2013 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.

Notice that, as $$78=2\cdot3\cdot13$$ and $$\gcd(2,3)=\gcd(3,13)=\gcd(2,13)=1$$, we can rewrite the original congruence this way: $$59x\equiv3\text{ (mod }78)\iff 59x\equiv3\text{ (mod }2)\text{ and }59x\equiv3\text{ (mod }3)\text{ and }59x\equiv3\text{ (mod }13) \iff x\equiv1\text{ (mod }2)\text{ and }x\equiv0\text{ (mod }3)\text{ and }7x\equiv3\text{ (mod }13).$$ We can now solve this congruence system using the Chinese remainder theorem to get the answer $$x\equiv45\text{ (mod }78)$$.