Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
I get that part hehe, what I dont get is why $41.59x \Rightarrow x$ –  user60334 Apr 11 '13 at 3: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$. –  1015 Apr 11 '13 at 3:15

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
    
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
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 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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