I Remainders, need Help proving a simple notion

1. Mar 10, 2016

mrandersdk

Hello

Today I looked at something that seems like it should have a simple solution, but I may have looked at for too long, and can't solve it. My problem is as follows.

When you devide a whole number by a whole number n, then it is clear that the possible remainders are 0,1,2,...n-1. If you then look at 7 devided by 5 you get remainder 2, 14 by five gives 4, 21 by 5 gives 1, 28 by 5 gives 3, and 35 by 5 gives 0, then the pattern repeats. That is all possible remainders is achieved by the first five multiplums of seven. I know it must have something to do with 5 and 7 being coprime. Because 18 and 15 shows a different pattern.

In general is it possible to show that if m is lager than m and n and m are coprime, then the first n multiplums of m devided by n, will always achieve all the possible remainders?

Are there anyway to prove what will in general happen to the pattern if n and m are not Co prime. It seems to me that all remainders are achieved, but one need to remove the remainders, in which the number that devides n and m, devides.

Hope my two questions Makes sense.

2. Mar 10, 2016

mathwonk

you are asking why 1.7, 2.7, 3.7, 4.7, 5.7 all have different remainders after divison by 5. do you know modular arithmetic? this is asking why none of those 5 numbers are equal mod 5. Well iof they were, then their difference would be zero mod 5. I.e. there would be a number k between 1 and 4, such that k.7 = 0 mod 5. This would be a number k such that 7.k is divisible by 5, and 0 < k < 5. Do you see why this cannot happen? can you generalize?

3. Mar 10, 2016

mrandersdk

Hey thanks i think i got it. I will take a closer look at it tommorrow and try to post the generalization

4. Mar 10, 2016

mathman

For your first question: If two numbers give the same remainder, then their difference is a multiple of the divisor, which makes the original numbers not coprime.