0
$\begingroup$

I have been stuck in a problem related to modular arithmetic. I have tried it using the generalized Euler's formula for $\gcd(a,b)=as+bt$, but have not reached the proof so far.

The question is:

Let $ a, b, n, n' $ all belong to integers($ \mathbb Z $) with $ n > 0 > , n' > 0 $ and $ \gcd(n, n') = 1 $. Show that if $ a \equiv b \mod n $ and $ a \equiv b \mod {n'} $ then $ a \equiv b \mod {nn'} $.

$\endgroup$
0
$\begingroup$

If $a \equiv b \mod n$ and $a \equiv b \mod n^\prime$, then there are integers $k$ and $k^\prime$ such that $kn = a - b = k^\prime n^\prime$. If $kn = k^\prime n^\prime$ and $(n,n^\prime) = 1$, then what is $(n,k^\prime)$?

$\endgroup$
  • $\begingroup$ i think if (n,n')=1 and kn=k'n' then should not k=n' and k'=n? $\endgroup$ – Bibekpandey Nov 24 '14 at 1:37
  • $\begingroup$ They aren't necessarily equal, but $n^\prime | k$ and $n | k^\prime$. So $a - b = mnn^\prime$, so what is $a - b \mod nn^\prime$? $\endgroup$ – Michael Biro Nov 24 '14 at 1:39
  • $\begingroup$ okay, i got it. Thank you man. $\endgroup$ – Bibekpandey Nov 24 '14 at 1:40

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.