3

So far this is my working out:
$n|a-a'$ and $n|b-b'$
So $n|(a-a')(b-b')$
Expanding: $n|ab-a'b-ab'+a'b'$
I'm not sure what to do next. I need to show that $n|ab-a'b'$

user112773
  • 81
  • 5

3 Answers3

6

We can write $a' = a + n k$ for some $k$, and likewise $b' = b + n m$; then

$$a'b' = (a + nk)(b + nm) = ab + n(\text{stuff}) \equiv ab \pmod{n}$$

upon distribution the multiplication.

  • Since $a \equiv a' \pmod{n}$,we can multiply both sides by b to get $ab \equiv a'b \pmod{n}$. By $ab \equiv a(mod n)b(mod n) \pmod{n}$,we can conclude that $ab \equiv a'b' \pmod{n}$[since $b\equiv b' \pmod{n}$ ]. Is this a correct approach? – rah4927 Dec 02 '13 at 08:22
3

In fact, $n^2$ divides your product, not helpful, as it turns out. Your strategy should have been to look at $ab-a'b'$ and show that it’s divisible by $n$. The trick is one you’ve probably seen already in calculus, to add and subtract a clever something. In this case, you write $ab-a'b'=ab-a'b+a'b-a'b'$, then factor the first pair and the second pair separately. Voilà.

Lubin
  • 62,818
1

Try it this way: since $n \mid (a - a')$, we have $a - a' = k_1 n$ for some integer $k_1$; thus $a = a' + k_1n$; likewise $b = b' + k_2 n$ for some $k_2$. Now when we take $ab$ we get:

$ab = a'b' + a'k_2n + k_1na + k_1k_2n^2$,

so we see that $n \mid (ab - a'b')$. QED.

Hope this helps. A jovial Yule season to one and all,

and of course,

Fiat Lux!!!

Robert Lewis
  • 71,180