Question

1. compute the least non-negative residue of 4^n (mod 9) for n=1,2,3,4,5.... prove that 6*(4^n)=6 (mod 9) for every n>0.

2. find nice tests for divisibility of numbers in base 34 by each of 2,3,5,7,11,and 17.

3. in Z/15Z, find all solutions of : (i) [36]X=[78]. (ii) [42]X=[57] (iii) [25]X=[36]

4. in Z/26Z, find the inverse of [9], [11], [17], and [22]

4. write the set of solutions of x=5 mod24. x=17 (mod 18)

for all equation line, there are triple line.

Answer 1

Ans 1)

(a) Least Residue non negative number are

4 for n=1

7 for n=2

1 for n=3

4 for n=4..

now terms will be repeat.

(b) The powers of 4 modulo 9 are

4, 4^2 ? 16 ? 7, 4^3 ? 7 · 4 ? 28 ? 1, 4^4 ? 4, . . . i.e. 4, 7, 1, 4, 7, 1, 4, 7, 1, . . .

But 6 · 4 ? 24 ? 6 mod 9, 6 · 7 ? 42 ? 6 mod 9 and 6 · 1 ? 6 mod 9.

Therefore, 6 · 4^n ? 6 mod 9 for all n ? 1.

Ans 2)

A number in base 34 looks like this: N = a^n · 34^n + a_(n?1) · 34^(n?1 )+ · · · + a_1 · 34 + a_0 where each coefficient a_i is a number 0 ? a_i ? 33.

Therefore, in this base:

1. N is divisible by 2 if a_0 is divisible by 2.

2. N is divisible by 3 if the sum of all coefficients a_i is divisible by 3 (because 34 ? 1 mod 3).

3. N is divisible by 5 if the alternating sum of the coefficients a_i is divisible by 5 (because 34 ? ?1 mod 5).

4. N is divisible by 7 if the alternating sum of the coefficients a_i is divisible by 7 (because 34 ? ?1 mod 7).

5. N is divisible by 11 if the sum of all coefficients a_i is divisible by 11 (because 34 ? 1 mod 11).

6. N is divisible by 17 if a_0 is 0 or 17 (because N ? a_0 mod 17 and 0 ? a_0 ? 33, so a_0 ? 0 mod 17 iff a_0 = 0 or 17).