3
$\begingroup$

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}$.

$\endgroup$
2
  • $\begingroup$ I get that part hehe, what I dont get is why $41.59x \Rightarrow x$ $\endgroup$
    – user60334
    Apr 11, 2013 at 3:07
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Julien
    Apr 11, 2013 at 3:15

3 Answers 3

2
$\begingroup$

$(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}$

$\endgroup$
6
  • $\begingroup$ oohh, similar answers at the same time, but with a different itemizing scheme. Let's see which listing method is preferred! $\endgroup$
    – davidlowryduda
    Apr 11, 2013 at 3:05
  • $\begingroup$ @mixedmath hehehehehehe! $\endgroup$
    – amWhy
    Apr 11, 2013 at 3:07
  • $\begingroup$ What I dont get in part (1) is how $41.59x \Rightarrow x$ $\endgroup$
    – user60334
    Apr 11, 2013 at 3:09
  • $\begingroup$ 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}$. $\endgroup$
    – amWhy
    Apr 11, 2013 at 3:12
  • 1
    $\begingroup$ 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$. $\endgroup$
    – amWhy
    Apr 11, 2013 at 3:16
1
$\begingroup$
  1. $41 \cdot 3 = 123$

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

$\endgroup$
0
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.