N 4

Art of Problem Solving

AoPS Online

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

N 4

G H J

Reveal topic tags

arithmetic sequence

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3615 posts

Peter

#1 h May 25, 2007, 12:25 AM • 3 Y

Y by UpvoteFarm, Adventure10, Mango247

Show that if an infinite arithmetic progression of positive integers contains a square and a cube, it must contain a sixth power.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

975 posts

#2 h Oct 21, 2007, 9:45 AM • 4 Y

Y by UpvoteFarm, Adventure10, Mango247, and 1 other user

Peter wrote:

Show that if an infinite arithmetic progression of positive integers contains a square and a cube, it must contain a sixth power.

http://www.kalva.demon.co.uk/short/soln/sh9715.html

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7579 posts

ZetaX

#3 h Oct 21, 2007, 11:51 AM • 4 Y

Y by UpvoteFarm, Adventure10, Mango247, and 1 other user

Let $r,s$ be coprime. If an arithmetic progression contains a $r$ -th power and a $s$ -th power, then it contains a $rs$ -th power.

Proof:
This is equivalent to: Let $a,d$ be integers. If there are integers $x,y$ such that $a \equiv x^r \equiv y^s \mod d$ , then there is an integer $z$ such that $a \equiv z^{rs} \mod d$ .

First observation: we can assume that $d=p^q$ is a prime power, $p$ prime.
Indeed, by the chinese remainder theorem, an integer polynomial equation can be solved $\mod n$ iff it can be solved $\mod$ all prime powers dividing $n$ . Here, the equations are $x^r-a , y^s-a, z^{rs}-a$ .

Second observation: let $d=p^q$ as said, then we can assume $\gcd(a,p^q)=1$ .
Indeed, if $p|a$ , we write $x= p^u x', y= p^v y'$ with $x', y'$ both not divisible by $p$ . Then $x^r \equiv y^s \mod p^q$ gives $a \equiv p^{ur} x'^r \equiv p^{vs} y'^s \mod p^q$ .
Thus either $a \equiv 0 \mod p^q$ , in this case we can take $z=0$ , or we get that $vs=v_p(x^r) = v_p(a) = v_p(y^s) = ur <q$ . This gives that $r|v$ , thus $vs=rsw$ for some $w$ , giving that we simply want to solve $z'^{rs} \equiv \frac{a}{p^{rsw}} \mod p^{q-rsw}$ with $\frac{a}{p^{rsw}}$ coprime to $p$ .

Third observation: the problem's statement is true if $a$ is coprime to $d$ .
Indeed, if $x^r \equiv a \equiv y^s \mod p^s$ and $p \nmid x,y$ , we write $1=ur+vs$ for some integers $r,s$ . Then we take $z=x^v y^u$ because then $z^{rs} = x^{vrs} y^{urs} \equiv a^{vs+ur} = a \mod d$ .

Putting all together, we solved the problem.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a