Had sent an entry on Euler's phi function earlier , and thought it would be best to follow this up with a slightly more detailed post on modulus arithmetic.
If we divide a number N by divisor p and get remainder r, we can write N = pq + r. In modulus arithmetic, we say that is N = r (mod) p.
r can take values from 0 to p-1. If the divisor is 12, the remainder can be anywhere from 0 to 11. If the remainder comes out as 13, this is the same as 1. If we compute the remainder as -5, this is the same as +7
Now, modulus is consistent for addition, subtraction & multiplication. What we mean by this is
If a = x mod p and
b = y mod p
- Then a+b = (x+y) mod p
- a-b = (x-y) mod p and
- ab = xy mod p
If the divisor is 12, the remainder can be anywhere from 0 to 11. If the remainder comes out as 13, this is the same as 1. If we compute the remainder as -5, this is the same as +7
Now, let us take this discussion on mod a little further. Now, let us assume two numbers a and b that are co-prime to each other. Further let us assume a = r mod b.
a= kb + r
HCF (a,b)= 1 => HCF (bk+r,b) = 1, this implies that HCF (r,b) =1. Or, in other words r and b have to be co-prime.
Let us think about this property with some examples. Let us take b = 12. Any number that leaves a remainder, say, 4 when divided by 12 can be written as a = 12n + 4 = 4(3n +1) , or a is a multiple of 4 => a cannot be co-prime with 12.
So, if we know a is co-prime with 12, then we can say that the only remainders possible when a is divided by 12 are 1, 5, 7,11 - Numbers that are co-prime with 12.
- Or, the number of possible remainders of a when divided by b, when a,b are coprime = phi (b). . A concept which we used to solve question no 3 in this set .
Further, if we say a,b are coprime. Any power of a will be co-prime with b. And So, a ^n will leave a remainder within the set of numbers that are lower than b and co-prime to b. Let us call this set Euler Set. Let us name the complement of this set the non-Euler set.
So, for 12, the Euler set will contain the elements 1,5,7,11. The non-Euler set will contain 0, 2,3,4,6,8,9,10.
- Any two numbers with mod within the Euler set will give a product with a modulus within the Euler set.
- If multiply n numbers together, and even one of the numbers leaves a remainder in the non-Euler set, the overall product will leave a remainder in the non-Euler set.
We have discussed some of the basic properties of mod in this post. Let us have a re-look Euler's Phi Function. There is another post on Euler's function here
Labels: CAT number theory, Euler's Phi Function, Modulus, Remainders