4
$\begingroup$

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 ?

Added Later :

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}$

Where is the fault in my reasoning? Please Help.

$\endgroup$
10
  • $\begingroup$ 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. $\endgroup$ – anon May 1 '15 at 19:42
  • 2
    $\begingroup$ @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 ? $\endgroup$ – MathGod May 1 '15 at 19:52
  • $\begingroup$ 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. $\endgroup$ – quid May 1 '15 at 19:55
  • $\begingroup$ I am very sorry but there is still a flaw in my argument. I retract it. At least for now. Sorry. $\endgroup$ – quid May 1 '15 at 20:34
  • $\begingroup$ @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 ? $\endgroup$ – MathGod May 1 '15 at 20:37
5
$\begingroup$

The problem is false as stated.

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – MathGod May 2 '15 at 8:25
  • $\begingroup$ Thanks. I've one last query before accepting your answer. Can you look at it? $\endgroup$ – MathGod May 3 '15 at 12:41
  • $\begingroup$ 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$. $\endgroup$ – Greg Martin May 3 '15 at 18:58

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.