7
$\begingroup$

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?

$\endgroup$
3
  • 6
    $\begingroup$ If n, n+1 are square-full then 4n(n+1), 4n(n+1)+1 are too. $\endgroup$ Nov 10, 2011 at 9:46
  • 2
    $\begingroup$ mathoverflow.net/questions/33037/… $\endgroup$
    – anon
    Nov 10, 2011 at 9:50
  • $\begingroup$ @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). $\endgroup$
    – robjohn
    Nov 10, 2011 at 15:46

2 Answers 2

19
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ You might want to add an initial pair to show existence :-) $\endgroup$
    – robjohn
    Nov 10, 2011 at 14:42
  • $\begingroup$ She added a list of square-full numbers, that is an initial pair enough. Anyway at this point I was not looking for a full proof but rather for ideas. The idea here is good enough. $\endgroup$ Nov 10, 2011 at 18:46
  • 1
    $\begingroup$ @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. $\endgroup$
    – robjohn
    Nov 11, 2011 at 0:19
  • 1
    $\begingroup$ Read comments better : isn't a list of square-full numbers an initial pair enough?... $\endgroup$ Nov 11, 2011 at 0:20
  • 2
    $\begingroup$ 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. $\endgroup$
    – Did
    Nov 11, 2011 at 7:36
11
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ $b_3=5$, right? So $2b_3^2$ wouldn't be square-full. $\endgroup$ Nov 10, 2011 at 11:48
  • $\begingroup$ @Gerry: Oops. I misread the definition of square-full. I will fix. $\endgroup$
    – robjohn
    Nov 10, 2011 at 12:28
  • $\begingroup$ A little too complicated, but thanks for trying. $\endgroup$ Nov 10, 2011 at 18:46
  • 1
    $\begingroup$ @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. $\endgroup$
    – robjohn
    Nov 11, 2011 at 0:21
  • 1
    $\begingroup$ Thanks for the upvote. The thought process was fairly straightforward. I needed two numbers that differed by $1$, and so that each had repeated prime factors. Pell's Equation $a^2-2b^2=\pm1$ came to mind. $a^2$ and $2b^2$ differ by $1$, and as long as $b$ is even, each prime factor appears at least twice in each. I solved the equation and since the $b$'s in the solution alternate between odd and even, I had to take every other solution (this was the change I made in response to Gerry's comment). Rather than simply saying that $(a_n,b_n)$ were solutions, I gave an inductive verification. $\endgroup$
    – robjohn
    Nov 11, 2011 at 0:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .