# Question regarding an IMO number theory solution

I am reading this Art of Problem Solving solution of an IMO question. I do not understand this statement "There exists no numbers $$1 such that $$m_1m_2\equiv1\text{ (mod }p^2\text{)}$$ as $$(p-2)(p-2) and $$2^2>1$$. Therefore, at most half of the values where $$a_0^{p-1}\equiv 1\text{ (mod }p^2\text{)}$$ are in range $$1. " where $$p\ge5$$ is a prime number. I understand the first sentence, but fail to see the second follows from that. Could someone please give an explicit derivation?

• If $m_1m_2 \equiv 1 \pmod{p^2}$, then there is some positive $k \in \mathbb{Z}$ such that $m_1m_2 = 1 + kp^2$. But $m_1m_2 \leq (p-2)^2 = p^2 -4p + 2^2 < p^2 +1\leq 1 + kp^2$. Commented Aug 23, 2022 at 5:18
• @mattstokes: I actually understand the first sentence of the quoted statements, but failed to see the second and how it followed from the first. You have not illuminated the dark part.
– Hans
Commented Aug 24, 2022 at 1:30

Suppose we have $$1 < m_1, m_2 leq p - 2$$. Then we have $$1 < m_1 m_2 \leq (p - 2)^2$$.

Now since $$p \geq 2$$, we have $$(p - 2)^2 = p^2 - 4p + 4 \leq p^2 - 4 < p^2$$. Thus, we have $$1 < 4 \leq m_1 m_2 \leq (p - 2)^2 < p^2$$. That is, $$1 < m_1 m_2 < p^2$$.

Now suppose $$m_1 m_2 \equiv 1 \mod p^2$$. Then there exists some integer $$j$$ with $$m_1 m_2 = 1 + j p^2$$. Since $$m_1 m_2 > 1$$, we must have $$j > 0$$. Then $$j \geq 1$$. But then we would have $$1 + p^2 \geq p^2 > m_1 m_2 = 1 + j p^2 \geq 1 + p^2$$. This is a contradiction.

I don’t see how the second half of the statement follows from the first half. However, since $$p$$ is odd, if $$a_0^{p -1} \equiv 1 \mod p^2$$ then $$(p^2 - a_0)^{p - 1} \equiv 1 \mod p^2$$. This is what is really needed to show that at most half the solutions $$0 \leq a_0 < p^2$$ can satisfy $$1 < a_0 \leq p - 2$$, since each such solution corresponds to another $$b_0 = p^2 - a_0$$ such that $$p^2 - p + 2 \leq b_0 < p^2 - 1$$ and the two ranges don’t overlap.

• Thank you. I had no problem with the first sentence of the quoted statement but the second sentence. I included the first sentence since it started with the preposition "therefore". It did not see the derivation. You agree with me on this part. The English description of the original solution is pretty ambiguous and vague...
– Hans
Commented Aug 24, 2022 at 1:33
• Do you care to consider my question on the following part of the solution? math.stackexchange.com/q/4517735/64809
– Hans
Commented Aug 24, 2022 at 15:51