# Proving there are infinitely many pairs of square-full consecutive integers

So the question goes like this :

A positive integer $n$ is called square-full if for every prime $p$, $p \, | \, n$ implies $p^2 \, | \, n$, i.e. every prime power factor of $n$ occurs at least at the second power. This is equivalent to saying that there is no prime $p$ such that $p \, \| \, n$.

Show that there are infinitely many consecutive pairs of square-full numbers, i.e. infinitely many $n$ such that $n$ and $n+1$ are square-full.

The context of the question highly suggests that this can be proved by induction and it is the solution that I am looking for. It is not a homework, just something that caught my attention because I couldn't find any natural answer to it... I hope I'm not missing something trivial!

I've tried assuming $n_1, n_2, \dots, n_k$ were the first $n_k$ integers such that $n_i$ and $n_i+1$ are square-full, and then generate some polynomial in those $2k$ integers to get a new couple $n_{k+1}$, $n_{k+1} + 1$ but after a few natural tries I got nothing good out of it. Any ideas?

-
If n, n+1 are square-full then 4n(n+1), 4n(n+1)+1 are too. – Angela Richardson Nov 10 '11 at 9:46
mathoverflow.net/questions/33037/… – anon Nov 10 '11 at 9:50
@anon: the solutions to $x^2-8y^2=1$ that are mentioned in one of the answers are what I give below (without worrying about 27). – robjohn Nov 10 '11 at 15:46

Any product of square-full numbers is square-full.

$4n(n+1)$ is square-full if n, n+1 are.
$4n(n+1)+1=4n^{2}+4n+1=(2n+1)^{2}$

list of square-full numbers at http://oeis.org/A060355

-
Thanks a lot =) – Patrick Da Silva Nov 10 '11 at 10:02
You might want to add an initial pair to show existence :-) – robjohn Nov 10 '11 at 14:42
@Patrick: Since Angela had given the inductive step, I was simply suggesting that an initial pair would make for a nice completion. I wasn't suggesting that her answer was wrong in any way. – robjohn Nov 11 '11 at 0:19
Read comments better : isn't a list of square-full numbers an initial pair enough?... – Patrick Da Silva Nov 11 '11 at 0:20
Putting aside the rudeness of the last comment, there is an inconsistency here: the OEIS contains the initial step of the recursion (there exist (nonzero) solutions) and the inductive step (if n is a solution, then 4n(n+1) is). Why reproduce the latter and not the former? (And why omit the argument that 4n(n+1)>n...) Additionally, I seem to remember that non self-contained answers are frowned upon on the site (and for very good reasons, if you ask me). Hence (as explained by @robjohn), mentioning at least one solution (and giving the link, of course) was clearly a better option. – Did Nov 11 '11 at 7:36

Suppose that $a_0=1$, $a_1=3$, $b_0=0$, and $b_1=2$. Let $a_n=6a_{n-1}-a_{n-2}$ and $b_n=6b_{n-1}-b_{n-2}$. Then $a_n^2-2b_n^2=1$ and $a_na_{n-1}-2b_nb_{n-1}=3$.

This means that $a_n^2$ and $2b_n^2$ are adjacent integers, and since $b_n$ is even both are obviously square-full for $n>0$.

Inductive Verification: \begin{align} a_n^2-2b_n^2 &=(6a_{n-1}-a_{n-2})^2-2(6b_{n-1}-b_{n-2})^2\\ &=(36a_{n-1}^2-12a_{n-1}a_{n-2}+a_{n-2}^2)-2(36b_{n-1}^2-12b_{n-1}b_{n-2}+b_{n-2}^2)\\ &=36(a_{n-1}^2-2b_{n-1}^2)+(a_{n-2}^2-2b_{n-2}^2)-12(a_{n-1}a_{n-2}-2b_{n-1}b_{n-2})\\ &=36+1-36\\ &=1 \end{align} and \begin{align} a_na_{n-1}-2b_nb_{n-1} &=(6a_{n-1}-a_{n-2})a_{n-1}-2(6b_{n-1}-b_{n-2})b_{n-1}\\ &=(6a_{n-1}^2-a_{n-1}a_{n-2})-2(6b_{n-1}^2-b_{n-1}b_{n-2})\\ &=6(a_{n-1}^2-2b_{n-1}^2)-(a_{n-1}a_{n-2}-2b_{n-1}b_{n-2})\\ &=6-3\\ &=3 \end{align}

-
$b_3=5$, right? So $2b_3^2$ wouldn't be square-full. – Gerry Myerson Nov 10 '11 at 11:48
@Gerry: Oops. I misread the definition of square-full. I will fix. – robjohn Nov 10 '11 at 12:28
A little too complicated, but thanks for trying. – Patrick Da Silva Nov 10 '11 at 18:46
@Patrick: you make it sound as if I've lost a competition. I am merely answering your question, and although not as concise as the recursive formula from the OEIS, it is still a valid, and I think worthwhile, answer. – robjohn Nov 11 '11 at 0:21
Sorry, maybe I wrote my comment the wrong way. What I meant was ; thanks for considering my question, your answer is just fine, but I just don't think it's very elegant. Angela's is wayy more. Although I'd be interested in knowing how you came up with such a thing. I upvoted it, just so you know. – Patrick Da Silva Nov 11 '11 at 0:27