Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If $ab \equiv 1 \pmod{p}$, is $a \equiv b \pmod{p}$?

I can see that $b$ is an inverse of $a$ modulo p. But what property does the inverse of $a$ has but $a\bar{a} \equiv 1 \pmod{p}$?

Thank you

share|improve this question
5  
Surely not. Did you try some examples? Try $a=2$ and $p=5$. –  lhf Apr 13 '11 at 3:32
    
@lhf: I was convinced by the other part of the proof but completely forgot a counter example ;). Thanks a lot. –  Chan Apr 13 '11 at 3:35
1  
Works fine if $p=2$ or $p=3$. For other $p$, there always are $a$, $b$ such that $ab\equiv 1$ but $a\not\equiv b$. –  André Nicolas Jun 29 '12 at 21:11

2 Answers 2

up vote 6 down vote accepted

No, $a$ is congruent to its inverse mod $p$ iff $a\equiv \pm 1 \bmod p$.

share|improve this answer

Consider a set $P = \{1, 2, 3, ...., p-1\}$; $|P|=p-1, p > 2$ is prime. Apart from $1$ and $p-1$, where $$1^2 ≡ (p-1)^2 ≡ 1 \pmod p,$$ consider further two positive integers $m$ and $n$ such that neither are multiples of $p$. Therefore each are congruent modulo $p$ to two of the $p-3$ members of $P$.

Now, $mn ≡ 1 \pmod p$ implies that $mn - 1 = kp$ for some positive integer $k$. This we can rewrite as $$mn - kp = 1$$ The equation $rx + sy = k (k, r, s, x, y ∈ ℕ)$ has solutions for $x$ and $y$ $\iff \gcd(x, y)$ divides $k$. In which case there are $\frac{k}{\gcd(x, y)}$ solutions. Since $\gcd(m,p) = \gcd(n, p) = 1$ (and of course $1|1$), the above equation has a unique solution for the positive integers $m$ and $n$. Now the only two members of $P$ which satisfy $$mn ≡ 1 \pmod p ⇒ m ≡ n \pmod p$$ are $$m, n ≡ 1 \pmod p \text{ and } m, n ≡ p-1 \pmod p$$ It follows that there are $\frac{p-3}{2}$ pairs of integers $m, n$ such that $$mn ≡ 1 \pmod p \text{ where } m ≢ n \pmod p$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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