Please answer in exercise 7.2 number 1 Only al xb in Z/nZ are as many as are the

Question

Please answer in exercise 7.2 number 1 Only

al xb in Z/nZ are as many as are the elements of Z/dZ. This finishes the proof of item (2. As usual, the case when pis a prime number is very simple: if a [0] in Z/pZ, then gcd(a, p) = 1, so the solution to laj.X-?is unique. Of course, if [al is the reciprocal of [a], which exists since [a] [0], then, that (unique) solution is given by Exercise 7.2 (1) Solve the congruences (i)AX 2 mod 6 () 4x1 mod 6 (iii) 4X 4 mod 6 (e) 256X 179 mod 337 iv) 3X800 mod 11 (vi) 1215X560 mod 2755. (2) Let p be a prime number, and a, b be integers such that 1 S a Sp-1. Prove that the congruence ax b mod p has a solution a-1mod p. Equations of Higher Degree in Z/nZ 7.2 7.2.1 General Remarks and Notations

Explanation / Answer

7.2. (1) note, ax=b (mod c) has a solution (unique) if and only if, gcd(a,c) divides b.

(i) 4x=2 (mod 6) has a unique solution since, gcd(4,6) = 2 divides 2 => 2x=1 (mod {6/gcd(4,6)} ) => 2x=1 (mod 3)

Multiplying by 2, we get, 4x = 2 (mod 3) , i.e. x=2 (mod 3)

So the solution is , x = 2 (mod 3)

i.e. x is of the form 2k+3 where k varies over the set of all integers

(ii) 4x=1 (mod 6) has no solution since gcd(4,6) = 2 which does not divide 1

(iii) same as (i) , 2x = 2 (mod 3) , multiplying by 2, we get, 4x = 4 (mod 3), i.e. x = 1 (mod 3), i.e. x is of the form 3k+1 for some integer k.

(iv) 3x = 800 = 8 (mod 11) , i.e. 3x = 8 (mod 11)

Multiplying by 4, we get, 12x = 32 (mod 11) , i.e. x = 10 (mod 11)

So, x is of the form 11k+10 for some integer k

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---