0
$\begingroup$

I'm given a multiple choice problem with 4 statements that could be each true or false. To help determining which ones are true or false I did some example problems which I will list here. I have made some guesses, however I'm not too confident in them. Any help would be appreciated.

a) 50 mod 7 = 1 AND 15 mod 7 = 1

Note that 50 = 10*5 and 15 = 3*5

b) 10 mod 7 = 3 AND 3 mod 7 = 3

c) 24 mod 11 = 2 AND 68 mod 11 = 2

Note that 24 = 6*4 and 68 = 17*4

d) 6 mod 11 = 6 AND 17 mod 11 = 6

e) 12 mod 5 = 2 AND 27 mod 5 = 2

Note that 12 = 4*3 and 27 = 9*3

f) 4 mod 5 = 4 AND 9 mod 5 = 4

g) 30 mod 3 = 0 AND 45 mod 3 = 0

Note that 30 = 6*5 and 45 = 9*5

h) 6 mod 3 = 0 AND 9 mod 3 = 0

i) 52 mod 7 = 3 AND 80 mod 7 = 3

Note that 52 = 13*4 and 80 = 20*4

j) 13 mod 7 = 6 AND 20 mod 7 = 6

Assume n represents the modulus, k represents a common factor and a,b are integers.

1. If n and k are relatively prime and if ak mod n = bk mod n, then a=b

2. If n and k are relatively prime and if ak mod n = bk mod n, then ak=bk

3. If n and k are relatively prime and if ak mod n = bk mod n, then a mod n = b mod n

4. If n and k are relatively prime and if ak mod n = bk mod n, then a mod n = ak mod n

MY ANSWERS: I think 1, 2, and 4 are all false, while 3 is true.

$\endgroup$

2 Answers 2

1
$\begingroup$

I suppose you are familiar with the definition that $a=b \mod m \Leftrightarrow m|(b-a)$. Take a look at number 1, for instance. We have:

$ak=bk \mod n \Leftrightarrow\\ n|(bk-ak)\Leftrightarrow\\ n|k(b-a) \Leftrightarrow (GCD(n,k)=1)\\ n|(b-a)$

Now, note that $n|(b-a)$ is not only an implication of $ak=bk\mod n$ but the statements are equivalent. Thus, you should be able to easily think of a counter-example, proving your guess that (1) is false.

I recommend you go about the other points the same way, they are not actually all that difficult.

(Your assumptions are correct, by the way, but until proven stay merely assumptions. Trouble with doing maths, I suppose, always having to prove everything...)

$\endgroup$
1
$\begingroup$

You are correct. A counterexample for 1,2 and 4 is $(a,b,k,n)=(9,2,4,7).$

3 is true because there exists an integer $m$ such that $$ak-bk=mn\iff (a-b)k=mn.$$ The left-hand-side has to be divisible by $n$. Since $k$ and $n$ are relatively prime, $a-b$ has to be divisible by $n$. Hence, $a-b\equiv 0\pmod n\iff a\equiv b\pmod n$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .