3

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

Jean-Claude Arbaut
  • 23,277
user60334
  • 717
  • I get that part hehe, what I dont get is why $41.59x \Rightarrow x$ – user60334 Apr 11 '13 at 03:07
  • 2
    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$. – Julien Apr 11 '13 at 03:15

3 Answers3

2

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

amWhy
  • 209,954
  • oohh, similar answers at the same time, but with a different itemizing scheme. Let's see which listing method is preferred! – davidlowryduda Apr 11 '13 at 03:05
  • @mixedmath hehehehehehe! – amWhy Apr 11 '13 at 03:07
  • What I dont get in part (1) is how $41.59x \Rightarrow x$ – user60334 Apr 11 '13 at 03: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 03:12
  • 1
    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 03:16
  • parentheses, I feel like I have learned a great secret today (+1) – davidlowryduda Apr 11 '13 at 09:04
1

  1. $41 \cdot 3 = 123$

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

davidlowryduda
  • 91,687
0

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