Track / Stage 6 / 131 of 400 #1131 of 2000

Problem 1131

National olympiad, first round

Number theory Difficulty 6.2 Prove it

. Let $p$ be a prime number.

a) Show that if $a \equiv b(\bmod p)$ , then $a^{p} \equiv b^{p}\left(\bmod p^{2}\right)$ .

b) How many integers $n \in\left\{1,2, \ldots, p^{2}\right\}$ are there for which the equation $x^{p} \equiv n\left(\bmod p^{2}\right)$ has at least one solution?

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

(arithmetic). a) We write $a=b+k p$ where $k$ is a certain integer and we expand:

$a^{p}=(b+k p)^{p}=b^{p}+\sum_{i=1}^{p}\binom{p}{i} b^{i}(k p)^{p-i}$

Each term in the last sum being divisible by $p$ , we indeed obtain $a^{p} \equiv b^{p}(\bmod p)$ . b) The goal is to determine how many distinct values the quantity $x^{p}\left(\bmod p^{2}\right)$ can take. According to the previous question, there are at most $p$ such values since two integers congruent modulo $p$ will give the same value. However, by Fermat's Little Theorem, we have $x^{p} \equiv x(\bmod p)$ , and thus from $x \not \equiv y(\bmod p)$ , we deduce $x^{p} \not \equiv y^{p}(\bmod p)$ and a fortiori $x^{p} \not \equiv y^{p}\left(\bmod p^{2}\right)$ . Therefore, there are at least $p$ values reached. Putting everything together, we can determine the answer to the question in the statement: it is $p$ .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.