Help prove this using modular arithmetic please!?

Question

Hi, I need help with this modular arithmetic statement. If anyone could expand on the modular arithmetic, too, I could learn a lot more than this problem. Thanks.

Let p be a prime number. Show that for any integer a: [a =/ 0 (mod p)] => [(there exist a b) such that (ab=1 (mod p))]

Answer 1

The requirement is equivalent to ab - pc = 1 for some constant c.

Take as an example the prime number p = 5.

The phrase "integer a not equal to zero (mod p)" means that a must not be a multiple of 5.



All possible values of a must therefore be one of the following 4 cases:-

1) a = 1 (mod 5)

2) a = 2 (mod 5)

3) a = 3 (mod 5)

4) a = 4 (mod 5)



1) If a = 1 (mod 5) then b = 1 is a solution of ab = 1 (mod 5)



2) 2b - 5c = 1 is a soluble Diophantine equation.

It is easy to see that b = 3 with c = 1 is one solution, and

increasing b by 5 to 8 while increasing c by 2 to 3 is another solution,

(because 2*8 - 5*3 = 1) so solutions for b take the form

b = 3 + 5k

If we replace a = 2 with a = 2 (mod 5) equivalent to a = 2 + 5t

we get another soluble Diophantine equation

2b - 5(c - bt) = 1 and solutions for b still take the form b = 3 + 5k



This process applies equally to remaining values for a not be a multiple of p.

We will always get a soluble Diophantine equation.



3) 3b - 5c = 1 is a soluble Diophantine equation.

It is easy to see that b = 2 with c = 1 is one solution, and

increasing b by 5 to 7 while increasing c by 3 to 4 is another solution,

Replacing a = 3 with a = 3 (mod 5) leaves result unchanged.

Solutions for b take the form b = 2 + 5k



4) 4b - 5c = 1 is a soluble Diophantine equation.

Observe that b = 4 with c = 3 is one solution, and

increasing b by 5 to 9 while increasing c by 4 to 7 is another solution,

(because 4*9 - 5*7 = 1)

Solutions for b take the form b = 4 + 5k



In general solutions to the linear Diophantine equation equations can always be found, and

if s represents any of p - 1 terms of the set {value a not a multiple of p} then the solutions for b will always take the form b = s + pk.



By finding the general form of this solution we have established that it exists.



Regards - Ian

Answer 2

If a ≠ 0 (mod p), p does not divide a. Hence, gcd(a,p) = 1. So there exist integers b and c such that ab + pc = 1, i.e., ab = 1 - pc = 1 (mod p).

Answer 3

n^5 - 5n^3 + 4n = n^5 - 5n^3 +5n -n = n(n^4-one million)-5n(n^2-one million) =n(n^2-one million)(n^2+one million-5) =n(n^2-one million)(n^2-4) = n(n+one million)(n-one million)(n+2)(n-2) =(n-2)(n-one million)n(n+one million)(n+2) you have 5 consecutive numbers, one is a multiple of two one is a multiple of three one is a multiple of four one is a multiple of 5 so it relatively is a multiple of two*3*4*5 = one hundred twenty ++++++++++++++++++++++++++++