Is my solution correct? Prove that an arithmetic progression contains the sixth power of some integer

Let $p$ and $q$ be distinct positive integers. Suppose $p^2$ and $q^3$ are terms of an infinite arithmetic progression whose terms are positive integers. Show that the arithmetic progression contains the sixth power of some integer

Let the progression have the form $a_n=a+nb$ then any term of the progression should be congruent to $a \mod b$

If $b$ divides $a$ then $q^6$ works
If not:
If $a=1$ then $q^3\equiv 1 \mod b$ and $q^6 \equiv 1 \mod b$

If $a \neq 1$ then there is $r>0$ such that $a^r \equiv a \mod b$ (would that be right?). So if $r$ is even, say $r=2k$ then we can take $(q^k)^6 = (q^3)^{2k}=a^r \equiv a \mod b$

If $r$ is odd $r=2k+3, \ \ \ k=0,1,...$ then $(q^kp)^6=(q^3)^{2k}(p^2)^3=a^{2k}a^3=a^r\equiv a \mod b$

• It's not in general true that there is an $r>1$ such that $a^r\equiv a\pmod b$. If you allow $r=1$, then $r=1$ always works. For example $3^r\not\equiv 3\pmod{18}$ for any $r>1$. – Thomas Andrews Nov 14 '16 at 23:39
• It always works only when $gcd(a,b)=1$ ? – user385043 Nov 15 '16 at 0:28

The part that does not work in general is finding $r>1$ so that $a^r=a \mod b$, as Thomas mentioned. This works as long as $\gcd(a,b)=1$. Then $a$ is in the unit group modulo $b$, i.e. $a \in (\mathbb{Z}/b\mathbb{Z})^\times$. So it has some order $k$ so that $a^k=1$, then $a^{k+1}=a$.

Now if $gcd(a,b) \neq 1$, we can show that for any common prime factor $p$, the higher power of $p$ dividing $a$ is a power of $p^6$. T

Using the Chinese Remainder Theorem, I can assume $b=p^k$ for some $k\geq 1$. $p|a$ so $a=0 \mod p$.

We know $a=x^2=y^3 \mod b$ (I changed p,q to x,y). The next few lines just show that the largest power of $p$ diving $a,x^2,y^3$ are all the same, assuming $p^k$ does not divide $a$.

Since $b=p^k$, we reduce modulo $p$ to get $a=x^2=y^3=0 \mod p$.

So $p|x$ and $p|y$.

Write $x=up^m,y=vp^n$ where $p$ does not divide $u$ and $v$.

Then $x^2=y^3 \mod p^k$ so $u^2p^{2m}=v^3p^{3n} \mod p^k$.

If $a=0 \mod p^k$, e get your other case, $b|a$.

Assume $a \neq 0 \mod p^k$ so that $2m,3n<k$.

So $2|m$ and $3|n$, i.e. $6|2m=3n$.

Writing $a=wp^s$ as we did for $x,y$, we see the powers of $p$ are the same for $a,x^2,y^3$ since they are all equal modulo $p^k$.

Therefore $6|s$ and we can write $a=w(p^t)^6$.

$\gcd(w,b=p^k)=1$ and $w=u^2=v^3$ (check this) so it is a sixth power by your argument. So altogether, $a$ is a sixth power modulo $b$.

I realized afterwards, I am just using the fact that $\mathbb{Z}/b\mathbb{Z}$ is a UFD. Afterwards, the proof is just like for $\mathbb{Z}$. So this is really a fact about UFDs with a finite unit group.