# How to prove that $a=z^{p}$ for some $z \in \mathbb{Z_{+}}$?

Claim :

If for a positive, composite integer $a$ and an odd prime $p$, such that $\gcd(a,p)=1$, we are given

$$a^{p^{n-2}(p-1)} \equiv 1 \pmod {p^n} \ \forall \ n \geq 2 \ \ ;\ n \in \mathbb{Z_{+}}$$

Then $a=z^{p}$ for some $z \in \mathbb {Z_{+}}$

Also note that the congruence holds for for all positive integers $n$, not just an arbitrary one.

My Approach :

At first a glance, it seems trivial to me, because by Euler's Theorem, $a^{\phi(p^{n})} \equiv 1 \pmod {p^n}$ and since $\phi(p^n) = p^{n-1}(p-1)$, I think that $a$ should be a perfect $p^{th}$ power to account for the extra $p$ in the power.

But, I don't have a formal proof for this. Is my reasoning enough or do I need a more rigorous argument ?

On observing more carefully, I found the following.

Let the prime factorization of $a$ is $\displaystyle \prod_{i=1}^{m} {q_{i}}^{k_{i}}$, where $q_{i}$ are prime factors of $a$. If we can prove that whenever the modular equation holds true, there exists at least one $k_{i} \geq p$, then we are done. This is because we can then write $a=j h^{p}$ and plugging it in the modular equation, we will get the same condition for $j$. This will set up an infinite descent and prove that $j=1$ and hence the claim will hold true.

Query : As Mr. Greg Martin stated, the claim is false in general. However,

If the modular equation is true for a fixed $n$, then,

$a \equiv z^p \pmod {p^{n}}$

$\displaystyle \therefore a \equiv {k_{1}}^p \pmod {p}$

$a \equiv {k_{2}}^p \pmod {p^{2}}$
$.$
$.$
$.$
$a \equiv {k_{n}}^{p} \pmod{p^n}$

$\implies a = {k_{n}}^{p} + j p^{n}$

If we choose $n$ to be sufficiently large, then $j=0$

$\implies a={k_{n}}^{p}$

• If you think $a$ is a $p$ th power in the integers - certainly not. You're right that there is good reason to expect that $a$ might be a $p$th power, but everything is occurring mod $p^n$ and you are unjustified in believing it carries up to the integers. That is a wrong feeling to have. – anon May 1 '15 at 19:42
• @anon The congruence equation I've written can be simplified, according to Mr. quid's answer, into the fact that $a \equiv z^{p} \pmod{p^n}$ or $p^n | (a-z^{p}) \ \forall \ \ n\geq 2 \ ; \ n \in \mathbb{Z}$. If, in case my claim is not true, then $a-z^p$ will be divisible by all the numbers $p, p^2, p^3,.... \text{ad infinitum}$ and this would lead to a contradiction. What do you think ? – MathGod May 1 '15 at 19:52
• MathGod is not exactly this since the $z$ could depend on $n$; but I agree that @anon likely read the quantifiers as I did initially. – quid May 1 '15 at 19:55
• I am very sorry but there is still a flaw in my argument. I retract it. At least for now. Sorry. – quid May 1 '15 at 20:34
• @quid I was just reading the wikipedia article to better understand your answer, in the meanwhile you retracted it.... Btw, can you tell me what was the flaw in your argument ? – MathGod May 1 '15 at 20:37

Let $a$ be any integer such that $a^{p-1}\equiv1\pmod{p^2}$. Then $$a^{p(p-1)-1} = (a^{p-1}-1)\big( (a^{p-1})^{p-1} + (a^{p-1})^{p-2} + \cdots + (a^{p-1})^1 + 1 \big);$$ the first factor is divisible by $p^2$ by assumption, and the second factor is congruent to $p\pmod {p^2}$, hence is divisible by $p$. We conclude that $a^{p(p-1)}\equiv1\pmod{p^3}$ automatically.
Similarly, $$a^{p^2(p-1)-1} = (a^{p(p-1)}-1)\big( (a^{p(p-1)})^{p-1} + (a^{p(p-1)})^{p-2} + \cdots + (a^{p(p-1)})^1 + 1 \big)$$ is then divisible by $p^4$, etc. In short, one can prove by induction that if $a^{p-1}\equiv1\pmod{p^2}$, then automatically $a^{p^{n-2}(p-1)}\equiv1\pmod{p^n}$ for every $n\ge2$.
And $a^{p-1}\equiv1\pmod{p^2}$ certainly does not imply that $a$ must be the $p$th power of an integer. (Examine the pairs $(a,p) = (7,5)$ and $(a,p)=(17,3)$, for example.) And note that adding $p^2$ to $a$ preserves the congruence, so $(32,5)$ and $(57,5)$ and $(82,5)$ ... are all counterexamples as well; in particular, there are plentiful counterexamples where $a$ is not prime.
• Both the examples you have given have $a$ as a prime, whereas in my question, I want $a$ to be composite (which, unfortunately, I'd forgotten to add.) If your reasoning is correct, can you tell any example where $a$ is composite? Also, what's the flaw in Mr. Dosidis's answer ? His conclusion seems to contradict yours. – MathGod May 2 '15 at 8:25
• I could answer your query - but it will be more illuminating for you if you answer it yourself! Take one of the specific examples in my answer (or $(10,3)$, say) and actually calculate your $k_1,k_2,\dots$ and the corresponding values of $j$. – Greg Martin May 3 '15 at 18:58