CAT Number Theory – Modulus

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 in a question previously.
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 .

Related posts

  • Fermat’s Little Theorem and Euler’s Phi functionNovember 15, 2010 Fermat’s Little Theorem and Euler’s Phi function Fermat's Little Theorem states that if p is prime then a^p - a is a multiple of p. In other words, a ^ (p-1) = 1 mod p, whenever a is not a multiple of p The proof for this […] Posted in Number Theory
  • Permutations and CombinationsNovember 5, 2012 Permutations and Combinations Question Sum of three whole numbers a, b and c is 10. How many ordered triplets (a, b, c) exist? (This is a variant on the previous question that can be found here). Will post the […] Posted in Combinatorics
  • Number TheoryJuly 15, 2013 Number Theory Question What is the remainder when (13100 +17100) is divided by 25? A. 2 B. 0 C. 15 D. 8 Correct Answer: Choice (A) Explanation: What is the remainder when (13100 […] Posted in Number Theory
  • Question on Number TheoryOctober 8, 2014 Question on Number Theory Question A bus service runs from Chennai to Blr every third day with the first bus starting on Jan 1st. Another bus service runs from Chennai to Mumbai every 5th day starting from […] Posted in Number Theory

Leave a Reply

Your email address will not be published. Required fields are marked *