Modulo, congruences and primes - the love story

[Virtate]

Can somebody please give me a hint as to how to do the following proof please? I have no idea what to use or where to start :(

Suppose that p is a prime and a is an integer which is not divisible by p. Prove that there exists an integer b such that ba is congruent to 1 mod p^2.

Thank you.

T

 

[uart]

Have you done the proof for modulo p (instead of modulo p^2) yet? If not then it's probably best to start there and once you understand that one it's pretty easy to exdend that same concepts to the "modulo p^2" case

 

[Virtate]

No, I haven't... How does that one work?

 

[Icebreaker]

$$\gcd(a,p)=1\Rightarrow \exists u,v\in \mathbb{Z}:au+pv=1 \Rightarrow p|1-au$$

$$\Rightarrow au\equiv 1 (\bmod p)\Rightarrow [a]_p<u>_p=[1]_p</u>$$

 

[uart]

No, I haven't... How does that one work?

Start with the set of all integers that are non-zero module p. That is S_1 = {1,2,3,...,p-1}.

Now consider the new set (call it say S_a) that results from multiplying each element in S_1 by a, where a is not a multiple of p (which is the same thing as saying that "a" is an element of S_1, since we're doing everything in module-p).
That is S_a = {a, 2a, 3a,...,(p-1)a}

You need to prove that the set S_a is actually the very same set as S_1.That is, S_a has all the same elements (no repeats and none missing) as S_1. This is a really fundamental result, you need to understand this proof. Attack it in two steps. First prove that there are no zero elements in S_a and then prove that there are no repeats.

Proof by condradiction is very useful here. Also use the fundamental theorum of arithmetic (uniqueness of prime factorization) to prove those above two properties of S_a.