this problem was also used in 98 at a Romanian TST at which I took part btw ... I scored a big 0 on it

Not by me! Let $a$ be the first term and $d$ be the common difference. Suppose $a+id=xx$, $a+jd=yyy$. then $xx\equiv yyy\equiv a\ (\mod d)$. Let $\mathrm{gcd}(a,d)=m$, then $a=mr$, $d=ms$, and $\mathrm{gcd}(r,s)=1$. We will prove the conclusion by induction on $d$. The case $d=1$ is trivial as the sequence will contain all integers $\geq a$. Suppose the cases less than $d$ are true. 1. If $\mathrm{gcd}(m,s)=1$, then $\mathrm{gcd}(a,s)=1$. Hence $\mathrm{gcd}(x,s)=1=\mathrm{gcd}(y,s)$, which imply there is integer $n$ such that $ny\equiv x\ (\mod s)$. So $n^6a^2 \equiv n^6y^6 \equiv x^6 \equiv a^3 \ (\mod s)$, since $\mathrm{gcd}(a,s)=1$, we get $n^6\equiv a\ (\mod s)$. Also since $\mathrm{gcd}(m,s)=1$, there is an integer $k$ such that $ks\equiv -n\ (\mod m)$. Then $(n+ks)^6\equiv 0\equiv a\ (\mod m)$. Also, $(n+ks)^6\equiv n^6\equiv a\ (\mod s)$. Since $\mathrm{gcd}(m,s)=1$ and $d=ms$, we get $(n+ks)^6\equiv a\ (\mod d)$. Now we can increase $k$ by a large multiple of $m$ to make $n+ks>a$. Therefore $(n+ks)^6$ is in the sequence. 2. If $\mathrm{gcd}(m,s)>1$, let $p$ be the common prime factor of $m$ and $s$. Since $a=mr$, $d=ms$ and $\mathrm{gcd}(r,s)=1$, the exponent $\beta$ of $p$ in the prime factorization of $d$ is greater than the exponent $\alpha$ of $p$ in the prime factorization of $a$, i.e. $\beta > \alpha \geq 1$. Then $p^{\alpha}\mid a$ and $p^{\beta}\mid d$. Now $\alpha<\beta$ implies every term is divisible by $p^{\alpha}$, not by $p^{\alpha+1}$. In particular, $p^{\alpha} \parallel x^2, y^3$ imply $\alpha$ is a multiple of $6$. The progression $\frac{a}{p^6} + l \left(\frac{d}{p^6}\right),\ l=0,1,2,...,$ has common difference $\frac{d}{p^6} <d$ and contains integers $\left(\frac{x}{p^3}\right)^2$ and $\left(\frac{y}{p^2}\right)^3$. By induction hypothesis, this progression contains an integer $z^6$. Then $p^6z^6$ is in the original progression, completing the induction

wisemaniac wrote: show that each arithmetic progression including a perfect square and a perfect cube includes a power of 6 ??? $m^2, m^3, (2m^3 - m^2)$ is a counterexample.

The arithmetical progression is supposed to be infinite... Pierre.

See this post: http://www.mathlinks.ro/Forum/viewtopic.php?t=658 I have found a solution but it's not complet and I'm not sure it's correct: We have $a\neq 0$ and $gcd(a,r)=1$ (if not we can build an other sequence verifying this) $a+nr=x^2, a+mr=y^3$ $\Leftrightarrow a^{3k}\equiv (x{}^k){}^6 (r), a^{2k'}\equiv (y^k')^6 (r)$ There is a perfect sixth power iff it exists $k$ or $k'$ such that $a^{3k}$ or $a^{2k'}$ equals $a$ modulo $r$ If $\Phi(r)+1$ is divisible by $2$ or $3$ it's finished (take $k=(\Phi(r)+1)/3$ or $k'=(\Phi(r)+1)/2$) So $\Phi(r)+1\equiv 1$ or $5$ modulo $6$. If it's $5$ from $(a^5)^{\Phi(r)+1}\equiv a^5\Rightarrow a^{5\Phi(r)+1}\equiv a$ we have $5\Phi(r)+1$ divisible by $3$ it's finished. If $\Phi(r)\equiv 0(6)$, ... I have not yet found

pbornsztein wrote: The arithmetical progression is supposed to be infinite... Pierre. Is the problem asking for existence of $n^6$ or $6^n$ in the progression? The first makes more sense, the second is what was written at the beginning of the thread (but there should be counterexamples to this version, I think).

It is asking for some $n^6$... Pierre.

Quote: See this post: http://www.mathlinks.ro/Forum/viewtopic.php?t=658 This contained: Quote: Not by me! Let a be the first term and d be the common difference. Suppose a+id=xx, a+jd=yyy then xx=yyy=a(mod d) Let gcd(a,d)=m, then a=mr, d=ms, and gcd(r,s)=1 We will prove the conclusion by inductino on d. The case d=1 is trivial as the sequence will contain all integers geqa. Suppose the cases less than d are true. 1. If gcd(m,s)=1, then gcd(a,s)=1. Hence gcd(x,s)=1=gcd(y,s), which imply there is integer n such that ny=x(mod s). So n6a2=n6y6=x6=a3(mod s), since gcd(a,s)=1, we get n6=a(mod s). Also since gcd(m,s)=1, there is an integer k such that ks=-n(mod m). Then (n+ks)6=0=a(mod m). Also, (n+ks)6=n6=a(mod s). Since gcd(m,s)=1 and d=ms, we get (n+ks)6=a(mod d). Now we can increase k by a large multiple of m to make n+ks>a. Therefore (n+ks)6 is in the sequence. 2. If gcd(m,s)>1, let p be the common prime factor of m and s. Since a=mr, d=ms and gcd(r,s)=1, the exponent \beta of p in the prime factorization of d is greater than the exponent \alpha of p in the prime factorization of a, i.e. \beta > \alpha geq1. Then p\alpha|a and p\beta|d. Now \alpha<\beta implies every term is divisible by p\alpha, not by p\alpha +1. In particular, p\alpha||x2, y3 imply \alpha is a multiple of 6. The progression a/p6 + l(d/p6), l=0,1,2,..., has common difference d/p6 <d and contains integers (x/p3)2 and (y/p2)3. By induction hypothesis, this progression contains an integer z6. Then p6z6 is in the original progression, completing the induction. Is this correct? If it is can someone break down the process for me?

Hmmm proof is imcomplete but it seems that you are definitely on the right track. Since it is already solved you really don't have to bother.

I forget something, we can multiplie the 2 equalities: $a^{3k}\equiv (x{}^k){}^6 (r), a^{2k'}\equiv (y^k')^6 (r)$ so $a^{3k+2k'} \equiv (x{}^ky{}^k')^6(r)$ and with $6|\Phi(r)$, $3k+2k'=6k''n+1$ is solvable for $n$ fixed

There we go. Much better now.

The difference between x^3 and x^2 is x^2(x-1) so we know after a certain amount of terms we will have a difference of (x^2)(x-1). The difference between x^6 and x^3 is (x^3)(x^3-1). Since (x^3)(x^3-1) is divisible by (x^2)(x-1), we know after adding a certain amount of terms we will get from x^3 to x^6.

But we don't know that the bases of the square and the cube are the same!

t0rajir0u wrote: But we don't know that the bases of the square and the cube are the same! Oh sorry, I didn't know it could be in a different base than 10.

No, no. You gave the square and the cube as $ x^2, x^3$. But they could be $ x^2, y^3$ where $ x \neq y$ and then your argument is invalid. (I was using "base" in the exponential sense - $ b$ is the base of the expression $ b^a$ - and not in the number-theoretic sense. Squareness and cubeness are properties that are independent of the base representation.)

Oh oops. Guess I read the problem wrong.

I believe this works as well, though I'm not 100% sure. The problem statement says there exist positive integers $a$, $b$, $x$, $y$, such that $x^2 \equiv y^3 \equiv b \pmod{a}$. Let $n = \text{ord}_{a}(b)$. If $n=1$, then $x^6 \equiv 1 \pmod{a}$, and we are done. If $n=2$, then $(xy)^6 \equiv b^5 \equiv b \pmod{a}$ and we are done. So assume $n>2$. Note that for any positive integer $k$, $l$, we have $(x^k y^l)^6 \equiv (x^2)^{3k} (y^3)^{2l} \equiv b^{3k+2l} \pmod{a}$. By the Chicken McNugget theorem, there exists $k$, $l$ such that $3k+2l = m$ for all $m> 6-2-3=1$; in particular, $3k_0+2l_0 = n-1$ for some $k_0$, $l_0$. Then we see $(x^{k_0} y^{l_0})^{6(n-1)} \equiv b^{(n-1)^2} \equiv b \pmod{a}$. Thus $(x^{k_0 (n-1)} y^{l_0 (n-1)})^6$, a sixth power, is in our arithmetic progression.

See here for generalization.

Here's a weird solution that I believe works. It suffices to prove the statement for prime powers. Our goal is to show that b is a quadratic residue $\mod p$ (show that $b^3$ is actually a sixth power $\mod p$). Suppose that $a^2 \equiv b^3 \mod p^k$. If $p|a, p|b$ then $p^6|a^2,b^3$ because of their lcm. Otherwise, suppose $a$ and $b$ are not divisible by $p$. Then raise each side to the $\frac{p-1}{2}$ power, yielding $1 \equiv b^{\frac{3p-3}{2}} \equiv b^{\frac{p-1}{2}}$ by Fermat's Little Theorem. Hence $ord_p(b)|\frac{p-1}{2}$, implying that $b$ is a quadratic residue. Therefore, setting $b \equiv x^2 \mod p$ gives the desired.

Does taking mod d to get "if y^3=x^2 mod d, then prove tehre exists z^6=x^2 mod d" where d is a common difference, noting that its suitable to prove for powers of primes and multiplicative group for power of primes is cyclic, then taking group isomorphism to get "if 3y=2x mod (d-1)(d^(n-1)), then prove there exists a 6z=2x mod (d-1)(d^(n-1))" which is trivial work?