Question

Let’s define a new number system, where we represent a number by the remainder we get on
dividing by successive primes, i.e., by 2, 3, 5, 7, 11, 13, 17, etc. Thus, 15 might be represented as
[1,0,0], and 27 might be [1,0,2].

1.) What numbers do [1, 1, 1, 1] and [1, 2, 3, 4] represent? Are the representations unique? What
other numbers might these lists represent?

2.) We know that 15 + 27 = 42. What is the representation of 42? Can you see how to get this from
the representations for 15 and 27?

Answer 1

1.) What numbers do [1, 1, 1, 1] and [1, 2, 3, 4] represent? Are the representations unique? What
other numbers might these lists represent?

=> Clearly the representations will all not be unique in this new number system.only some will have unique representations.

As [1,1,1,1] can be any number which is having a remainder of 1 on dividing it with the first four primes (2,3,5,7),

so when we multiply all these primes i.e ( 2 * 3 * 5 * 7) = 210. So now if we add one to this number then it is "211".

now 211 when divided by either 2 or 3 or 5 or 7, we get one as the remainder.

So 211 is represented as [1,1,1,1].

Similarly if we multiply the number 210 with any of the multiples of the primes used to represent it and then add 1 to the number obtained we get another number which is having a remainder of 1 on dividing it with the first four primes (2,3,5,7).

for e.g (210*2+1) = 421 will also be represented by [1,1,1,1].

Similarly [1,2,3,4] , now we want to find a solution to x where

x%2=1      x%3=2 x%5=3 x%7=4

we use the "Chinese Remainder Theorem" ,

Since 2, 3, 5, and 7 are pairwise relatively prime, the Chinese Remainder Theorem tells us that there is a unique solution modulo m, where m = 2*3*5*7 = 210

We apply the technique of the Chinese Remainder Theorem with k = 4,

m1 = 2, m2 = 3, m3 = 5, m4 = 7 and

a1 = 1, a2 = 2, a3 = 3, a4 = 4

z1 = m / m1 = m2*m3*m4 = 3*5*7 = 105

z2 = m / m2 = m1*m3*m4 = 2*5*7 = 70

z3 = m / m3 = m1*m2*m4 = 2*3*7 = 42

z4 = m / m4 = m1*m2*m3 = 2*3*5 = 30

( Inverse of a number "n" modulo number "y" is a number "f" such that (f*n)mod(y) = 1 )

y1 ≡ z1 ^-1 (mod m1) ≡ 150^-1 (mod 2) ≡ Modular inverse does not exist i.e no solution exists

y2 ≡ z2 ^-1(mod m2) ≡ 70^-1 (mod 3) ≡ 1

y3 ≡ z3 ^-1 (mod m3) ≡ 42^-1 (mod 5) ≡ 3

y4 ≡ z4 ^-1 (mod m4) ≡ 50^-1 (mod 7) ≡ 1

If had there been all the values present, following steps needs to be performed in order to find the value x,

w1 ≡ y1z1 (mod m)

w2 ≡ y2z2 (mod m)

w3 ≡ y3z3 (mod m)

w4 ≡ y4z4 (mod m)

The solution, which is unique modulo m, is

x ≡ a1w1 + a2w2 + a3w3 + a4w4 (mod m)

so there cannot be a number which can be represented as [1,2,3,4] in this number system.

*********************************************************************************************************************************

2.) We know that 15 + 27 = 42. What is the representation of 42? Can you see how to get this from
the representations for 15 and 27?

let us represent both the numbers as remainders when divided by numbers

[ 2,3,5,7,11,13 ]

15 ==========> ( 1,0,0,1, 4, 2)

27 ==========> ( 1,0,2,6, 5, 1)

42 ==========> ( 0,0,2,0, 9, 3)

so now if you observe, the first digits in all the above representations, we have

1 for 15

1 for 27

and if we add them (1+1) and divide this result by 2, the remainder obtained is 0, which is the first digit for 42.

similarly for every consecutive digits in the representation we can see this result being satisfied.

( 0 + 0 ) % 3 = 0 which is second digit in representation of 42.

( 0 + 2 ) % 5 = 2 which is third digit in representation of 42.

( 1 + 6 ) % 7 = 0 which is fourth digit in representation of 42.

( 4 + 5 ) % 11 = 9 which is fifth digit in representation of 42.

( 2 + 1 ) % 13 = 3 which is sixth digit in representation of 42.