1
$\begingroup$

The question is

Suppose p is a prime number and p does not divide a. Prove that the congruence $ax \equiv 1 \mod p$ has a solution

(Without using Fermat's Theorem), I can intuitively tell this is true because since $p$ is prime, every $x < p$ is co-prime to it, thus $$x \mod p$$ Will produce a unique integer for each $x \in \{0, 1, 2, .... p-1\}$, before it cycles over again at $p$. Clearly, some $x$ must have that $x \mod p = 1$. However, I don't know how to prove this for $ax$, mainly because I can't prove the ramifications it can have on the mod cycle. What I do know is that if for some $x$, we have: $$ax \equiv ay \mod p$$ Then since $p$ doesn't divide $a$ (by question assumption), it must divides $x - y$, implying that the solution for $ax \equiv 1 \mod p$ only depends on $x$, however, I don't know how to show this rigorously. Could anyone enlighten me?

$\endgroup$
1
  • $\begingroup$ Why "without flt"? Flt tells us $a^{p-2}a\equiv 1$ so there's nothing to prove. To understand just go through the proof of flt. $\endgroup$ – fleablood Oct 19 '16 at 3:36
5
$\begingroup$

Let's consider the numbers $-1,a-1,2a-1, \ldots (p-1)a-1$. These must have different remainders $\mod p$, since otherwise $ma \equiv na \mod p \implies p|a(m-n)$, but $p \nmid a$ and $0<|m-n|<p$, so this can't happen.

Therefore, they must leave $p-1$ different remainders $\mod p$. There are $p$ of these numbers, and $p$ possible remainders, so one of these must leave the remainder $0 \mod p$. That value of $x$ solves the equation.

$\endgroup$
1
$\begingroup$

Since $\gcd(a,p)=1$ Bézouts lemma assures us that there exists $x,y$ s.t. $xa+yp = 1$ . Taking this equation mod $p$ solves your question.

$\endgroup$
0
$\begingroup$

Hint $ $ Your argument shows that the map $\,x \mapsto ax\,$ is injective ($1$-$1$) on the integers mod $p.\,$ Thus, by the Pigeonhole Principle, it is surjective (onto), so it takes the value $1,\,$ i.e. $\,ax\equiv 1$ for some $x$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.