The Modulo representation of numbers :
The Modulo representation is one that is very different
from the place value system.
Consider any three numbers which are relatively prime to each other. Relatively prime
numbers are those numbers which have no common factors. The numbers need not necessarily
be prime. Examples of relatively prime numbers are -
1) 2, 3, 5
2) 5, 7, 9
3) 9, 16, 25 (note here that 9,16 and 25 are not prime, but they have no common factors
and hence, are relatively prime to each other)
Coming back to modulo representations, let us try to
understand it with an example.
Consider the 3 numbers 2, 3 and 5.
The LCM of these numbers is 2 × 3 × 5 = 30.
So, any number from 0 to 29 can be represented in terms of its remainder with respect to
each of 2, 3 and 5.
Take the number 23. The remainder when
i) 23 is divided by 2 is 1.
ii) 23 is divided by 3 is 2.
iii) 23 is divided by 5 is 3.
Hence, 23 can be represented as (1, 2, 3).
This is called a triplet as there are 3 numbers to represent another
number. Each number from 0 to 29 will have a unique triplet to represent it. Numbers
greater than 29 will have repeating representations, identical to those between 0 and 29.
For example, the representation for 31 is (1, 1, 1) which is the same as that for 1.
Let us look at another number - say 3.
i) 3 leaves a remainder of 1 when divided by 2.
ii) 3 leaves a remainder of 0 when divided by 3.
iii) 3 leaves a remainder of 3 when divided by 5.
The representation for 3 in this system is (1, 0, 3).
Addition
Supposing we wish to find the sum of 23 & 3. Just adding the triplets for 23 & 3
will give the triplet for the sum. This is a little tricky, though. Watch carefully how it
has to be done !
23 + 3= (1, 2, 3) + (1, 0, 3) = (2, 2, 6)
- just add the corresponding remainders when divided by 2,3 and 5.
In this triplet, the 1st number represents the
remainder when divided by 2, the second the remainder when divided by 3 and the third, the
remainder when divided by 5.
However, the remainder when divided by 2 can never be greater than 1,
that when divided by 3 can never be greater then 2 & that when
divided by 5 can never be greater than 4.
So, the solution we have obtained above, has to be reduced further. For that, take each
number in the representation of the sum. If it is greater than the allowed limit, take the
modulo of that number again.
So, for (2, 2, 6),
i) 2 > 1, which is the maximum possible remainder when divided by 2. Hence [2]2=0.
ii) 2 = 2, which is the maximum possible remainder when divided by 3.So,let's leave it as
it is!
iii) 6 > 4, which is the maximum possible remainder when divided by 5. Hence [6]5=
1.
Hence the representation for 23 + 3 =26 is (0, 2, 1).
Subtraction
If we wish to subtract 3 from 23,
23 -3 = (1, 2, 3) - (1, 0, 3) = (0, 2, 0)
- just subtract the respective remainders.
Thus, 20 = (0,2,0)
Now, let us see what to do if we get a negative number
in the remainder.
Take the example 17 - 9.
17 = (1, 2, 2)
9 = (1, 0, 4)
17 - 9 = (1, 2, 2) - (1, 0, 4) = (0, 2, -2)
Now, we have -2 as the remainder when divided by 5. As
in addition, the modulo has to be found for -2. But, how do you find the modulo of a
negative numer ? Well, it's very simple !
Add the base to the remainder. In this case, the base is 5 and the remainder is -2.
Adding, we get 3. Now, take the modulo of 3 with respect to the base 5 i.e.[3] 5.
The result is 3.
Hence 17 - 9 = 8 = (0, 2, 3).
Multiplication
Multiplication is as simple as addition and subtraction. Just multiply the
respective remainders!
Take the numbers 4 and 7.
4 = (0, 1, 4)
7 = (1, 1, 2)
4 × 7 = (0, 1, 4) × (1, 1, 2) = (0, 1, 8)
As before, the remainders must be less than the
allowable limit. Here 8 > 4, which is the maximum possible remainder when divided by 5.
Taking [8] 5, we get 3.
Hence 4 × 7 = 28 = (0, 1, 3)
This representation will hold for any number of bases relatively prime to each other. For example, if we wish to represent a number with respect to 4 bases, we will have 4 numbers in the representation.
Now, go on to Indeterminate equations !