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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.