%\usepackage{amsmath,amssymb,amsbsy,amsfonts,amsthm,latexsym,amsopn,amstext,amsxtra,euscript,amscd} %\renewcommand{\theequation}{\arabic{equation}} %\begin{document} %\newtheorem{prop}{Proposition} %\newtheorem{lem}[prop]{Lemma} %\newtheorem{cor}[prop]{Corollary} %\newtheorem{conj}[prop]{Conjecture} %\newtheorem{defi}[prop]{Definition} %\newtheorem{thm}[prop]{Theorem} %\newtheorem{fac}[prop]{Fact} %\newtheorem{facs}[prop]{Facts} %\newtheorem{com}[prop]{Comments} %\newtheorem{prob}{Problem} %\newtheorem{problem}[prob]{Problem} %\newtheorem{ques}{Question} %\newtheorem{question}[ques]{Question} %\newtheorem{remark}[prop]{Remark} %% DEFINITIONS \documentclass[12pt,reqno]{article} \def\fmod#1 #2{#1\; ({\rm mod}\ #2)} \def\divides{ \, | \, } \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf Powerful Values of Quadratic Polynomials } \vskip 1cm \large Jean-Marie De Koninck and Nicolas Doyon \\ D\'epartment de Math\'ematiques \\ Universit\'e Laval \\ Qu\'ebec, PQ G1V 0A6 \\ Canada \\ \href{mailto:jmdk@mat.ulaval.ca}{\tt jmdk@mat.ulaval.ca} \\ \href{mailto:nicolas.doyon.1@ulaval.ca}{\tt nicolas.doyon.1@ulaval.ca} \\ \ \\ Florian~Luca \\ Instituto de Matem{\'a}ticas\\ Universidad Nacional Aut\'onoma de M{\'e}xico \\ C. P. 58180\\ Morelia, Michoac{\'a}n \\ M{\'e}xico \\ \href{mailto:fluca@matmor.unam.mx}{\tt fluca@matmor.unam.mx}\\ \end{center} \vskip .2 in \begin{abstract} We study the set of those integers $k$ such that $n^2+k$ is powerful for infinitely many positive integers $n$. We prove that most integers $k$ have this property. \end{abstract} \def\scr{\scriptstyle} \def\\{\cr} \def\({\left(} \def\){\right)} \def\[{\left[} \def\]{\right]} \def\<{\langle} \def\>{\rangle} \def\fl#1{\left\lfloor#1\right\rfloor} \def\rf#1{\left\lceil#1\right\rceil} \def\Z{\mathbb Z} \def\Zx{\Z[[X]]} \def\Q{\mathbb Q} \def\Qx{\Q(\hskip-1pt(X)\hskip-1pt)} \def\R{\mathbb R} \def\N{\mathbb N} \def\F{\mathbb F} \def\Fx{\F(\hskip-1pt(X)\hskip-1pt)} \def\Fq{\F_q} \def\Fqx{\Fq(\hskip-1pt(X)\hskip-1pt)} \def\K{\mathcal K} \def\Kx{\K[[X]]} \def\cS{\mathcal S} \def\e{{\bf e}} \def\cR{\mathcal R} \def\cP{\mathcal P} \def\cQ{\mathcal Q} \def\cT{\mathcal T} \def\ord{{\mathrm{ord}\,}} \def\ct{{\mathrm{cont}\/}} \def\eps{\varepsilon} \def\ep{{\mathbf{\,e}}_p} \def\epp{{\mathbf{\,e}}_{p-1}} \def\dat{20 f\'evrier 2011} \def\xxx{\vskip5pt\hrule\vskip5pt} \def\yyy{\vskip5pt\hrule\vskip2pt\hrule\vskip5pt} \newcommand{\comm}[1]{\marginpar {\fbox{#1}}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%% STANDARD STUFF %%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % use the AMS-Euler Fraktur fonts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newfont{\teneufm}{eufm10} \newfont{\seveneufm}{eufm7} \newfont{\fiveeufm}{eufm5} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % allow automatic size selection in math mode % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newfam\eufmfam \textfont\eufmfam=\teneufm \scriptfont\eufmfam=\seveneufm \scriptscriptfont\eufmfam=\fiveeufm %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % \frak works on a single symbol at a time... % \def\frak#1{{\fam\eufmfam\relax#1}} % %%%%%%%%%%%%%%%%%%% bbb-matter \def\bbbr{{\rm I\!R}} %reelle Zahlen \def\bbbc{{\rm I\!C}} %complex cisla \def\bbbm{{\rm I\!M}} \def\bbbn{{\rm I\!N}} %natuerliche Zahlen \def\bbbf{{\rm I\!F}} \def\bbbh{{\rm I\!H}} \def\bbbk{{\rm I\!K}} \def\bbbl{{\rm I\!L}} \def\bbbp{{\rm I\!P}} \newcommand{\lcm}{{\rm lcm}} \def\bbbone{{\mathchoice {\rm 1\mskip-4mu l} {\rm 1\mskip-4mu l} {\rm 1\mskip-4.5mu l} {\rm 1\mskip-5mu l}}} \def\bbbc{{\mathchoice {\setbox0=\hbox{$\displaystyle\rm C$}\hbox{\hbox to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}} {\setbox0=\hbox{$\textstyle\rm C$}\hbox{\hbox to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}} {\setbox0=\hbox{$\scriptstyle\rm C$}\hbox{\hbox to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}} {\setbox0=\hbox{$\scriptscriptstyle\rm C$}\hbox{\hbox to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}}}} \def\bbbq{{\mathchoice {\setbox0=\hbox{$\displaystyle\rm Q$}\hbox{\raise 0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.8\ht0\hss}\box0}} {\setbox0=\hbox{$\textstyle\rm Q$}\hbox{\raise 0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.8\ht0\hss}\box0}} {\setbox0=\hbox{$\scriptstyle\rm Q$}\hbox{\raise 0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.7\ht0\hss}\box0}} {\setbox0=\hbox{$\scriptscriptstyle\rm Q$}\hbox{\raise 0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.7\ht0\hss}\box0}}}} \def\bbbt{{\mathchoice {\setbox0=\hbox{$\displaystyle\rm T$}\hbox{\hbox to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}} {\setbox0=\hbox{$\textstyle\rm T$}\hbox{\hbox to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}} {\setbox0=\hbox{$\scriptstyle\rm T$}\hbox{\hbox to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}} {\setbox0=\hbox{$\scriptscriptstyle\rm T$}\hbox{\hbox to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}}}} \def\bbbs{{\mathchoice {\setbox0=\hbox{$\displaystyle \rm S$}\hbox{\raise0.5\ht0\hbox to0pt{\kern0.35\wd0\vrule height0.45\ht0\hss}\hbox to0pt{\kern0.55\wd0\vrule height0.5\ht0\hss}\box0}} {\setbox0=\hbox{$\textstyle \rm S$}\hbox{\raise0.5\ht0\hbox to0pt{\kern0.35\wd0\vrule height0.45\ht0\hss}\hbox to0pt{\kern0.55\wd0\vrule height0.5\ht0\hss}\box0}} {\setbox0=\hbox{$\scriptstyle \rm S$}\hbox{\raise0.5\ht0\hbox to0pt{\kern0.35\wd0\vrule height0.45\ht0\hss}\raise0.05\ht0\hbox to0pt{\kern0.5\wd0\vrule height0.45\ht0\hss}\box0}} {\setbox0=\hbox{$\scriptscriptstyle\rm S$}\hbox{\raise0.5\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.45\ht0\hss}\raise0.05\ht0\hbox to0pt{\kern0.55\wd0\vrule height0.45\ht0\hss}\box0}}}} \def\bbbz{{\mathchoice {\hbox{$\sf\textstyle Z\kern-0.4em Z$}} {\hbox{$\sf\textstyle Z\kern-0.4em Z$}} {\hbox{$\sf\scriptstyle Z\kern-0.3em Z$}} {\hbox{$\sf\scriptscriptstyle Z\kern-0.2em Z$}}}} \def\ts{\thinspace} %\newenvironment{proof}{\noindent{\it Proof. }}{{\qed}} \def\squareforqed{\hbox{\rlap{$\sqcap$}$\sqcup$}} \def\qed{\ifmmode\squareforqed\else{\unskip\nobreak\hfil \penalty50\hskip1em\null\nobreak\hfil\squareforqed \parfillskip=0pt\finalhyphendemerits=0\endgraf}\fi}%% %%%%%%%%%%%%%%%%%%%%%%%%% % Alphabet calligraphic % %%%%%%%%%%%%%%%%%%%%%%%%% \def\cA{{\mathcal A}} \def\cB{{\mathcal B}} \def\cC{{\mathcal C}} \def\cD{{\mathcal D}} \def\cE{{\mathcal E}} \def\cF{{\mathcal F}} \def\cG{{\mathcal G}} \def\cH{{\mathcal H}} \def\cI{{\mathcal I}} \def\cJ{{\mathcal J}} \def\cK{{\mathcal K}} \def\cL{{\mathcal L}} \def\cM{{\mathcal M}} \def\cN{{\mathcal N}} \def\cO{{\mathcal O}} \def\cP{{\mathcal P}} \def\cQ{{\mathcal Q}} \def\cR{{\mathcal R}} \def\cS{{\mathcal S}} \def\cT{{\mathcal T}} \def\cU{{\mathcal U}} \def\cV{{\mathcal V}} \def\cW{{\mathcal W}} \def\cX{{\mathcal X}} \def\cY{{\mathcal Y}} \def\cZ{{\mathcal Z}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%% END OF STANDARD STUFF %%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} Given an arbitrary integer $k\neq 0$, Mollin and Walsh \cite{kn:mollinwalsh} have shown that there exist infinitely many ways of writing $k$ as a difference of two nonsquare powerful numbers. A positive integer $n$ is said to be {\it powerful} if $p^2 \divides n$ for each prime divisor $p$ of $n$. For instance, 17 has two such representations below $10^9$, namely $17=125-108$ and $17=173881809 - 173881792$. But what about representations $17=P-n^2$, where $P$ is a powerful number? It turns out that there are no such representation with $P<10^9$. However, in view of Theorem 1 (below) we believe that infinitely many such representations should exist, even though the smallest is probably very large (see Table 1 in Section 3). In general, identifying all those integers $k\neq 0$ such that $n^2+k$ is a powerful number for infinitely many positive integers $n$ seems to be a very difficult problem. Indeed, already showing that one such $n$ exists is not obvious. Now, for a given $k\neq 0$, if one can find an integer $n_0$ such that $n_0^2+k$ is a powerful number which is not a perfect square, that is if \begin{equation} n_0^2+k = m_0^2 b^3, \label{eq:ex1} \end{equation} for some integer $m_0$, with $b>1$ squarefree, then (\ref{eq:ex1}) can be written as \begin{equation} n_0^2 - D m_0^2 = -k , \label{eq:ex2} \end{equation} where $D>1$ is a cube but not a square. Now since $x^2-Dy^2=-k$ is a generalized Pell equation with a given solution (see, for instance, Robertson \cite{rob}), it must have infinitely many solutions, thus providing infinitely many $n$'s for which $n^2+k$ is powerful. However, given an arbitrary integer $k$, finding a minimal solution $(n_0,m_0)$ of (\ref{eq:ex2}) for an appropriate $D$ is not easily achieved. In this note, we use a different approach and show that for almost all integers $k$, there exist infinitely many positive integers $n$ such that $n^2+k$ is powerful. In fact, we prove the following result. \begin{theorem} \label{thm:main} For any positive real number $x$, let ${\cal P}(x)$ be the set of integers $k$ with $|k|\le x$ such that $n^2+k$ is powerful for infinitely many positive integers $n$. Then $2x-\#{\cal P}(x)=o(x)$. \end {theorem} Throughout this paper we use the Landau symbols $O$ and $o$ as well as the Vinogradov symbols $\gg$ and $\ll$ with their usual meaning. We let $\log_1 x=\max\{1,\log x\}$, where $\log$ stands for the natural logarithm, and for $i>1$ we define $\log_i x=\log_1\(\log_{i-1} x\)$. When $i=1$ we omit the subscript and thus understand that all the logarithms that will appear are $\ge 1$. For a positive integer $n$ we write $\phi(n)$ for the Euler function of $n$. \medskip \section{The Proof} For the proof, we first give a sufficient algebraic criterion on $k$ which insures that $n^2+k$ is powerful for infinitely many $n$. We then show that most integers $k$ satisfy this condition. \medskip We shall prove this only when $k>0$, but the argument extends without any major modification to the case $k<0$. \begin{proposition} \label{prop:alg} Assume that there exist positive integers $y_1$ and $d \divides ky_1^2+1$ such that $$ u=\frac{1}{2y_1}\left(\frac{ky_1^2+1}{d}-d\right) $$ is a positive integer coprime to $k$. Let $D=u^2+k$ and assume further that $y_1$ is coprime to $D$. Then there exist infinitely many positive integers $n$ such that $n^2+k$ is powerful. \end{proposition} \begin{proof} Since $u$ is an integer, it follows that $d$ and $(ky_1^2+1)/d$ are integers of the same parity. Put $$ x_1=\frac{1}{2}\left(\frac{ky_1^2+1}{d}+d\right). $$ One checks immediately that $x_1^2-(uy_1)^2=ky_1^2+1$, which can be rewritten as \begin{equation} \label{eq:ajouteq} x_1^2-Dy_1^2=1. \end{equation} Define the sequences $(x_m)_{m\ge 1}$ and $(y_m)_{m\ge 1}$ as $$ x_m+y_m{\sqrt {D}}=(x_1+y_1{\sqrt {D}})^m $$ for all $m\ge 1$. Then, for all $m\ge 1$, \begin{eqnarray} \label{eq:pell1} x_m^2-Dy_m^2& = & (x_m + y_m \sqrt D) (x_m - y_m \sqrt D) \\ \nonumber & = & (x_1+y_1 \sqrt D)^m (x_1- y_1 \sqrt D)^m \\ \nonumber & = & (x_1^2 - D y_1^2 )^m = 1 \end{eqnarray} We now search for positive integers $n$ such that $n^2+k=D\ell^2$ holds with some positive integer $\ell$ such that $D\divides \ell$. It is clear that such numbers $n$ have the property that $n^2+k$ is powerful. We rewrite this equation as \begin{equation} \label{eq:pell2} n^2-D\ell^2=-k. \end{equation} Noting that $u^2-D\cdot 1^2=-k$ and using \eqref{eq:pell1}, if $$ n+{\sqrt {D}}\ell =(u+{\sqrt {D}})(x_m+{\sqrt {D}}y_m), $$ one checks by multiplying each side by its conjugate that the pair $(n,\ell)$ satisfies \eqref{eq:pell2}. Expanding we get $$ n=ux_m+Dy_m\qquad {\text{\rm and}}\qquad \ell=uy_m+x_m. $$ It suffices to argue that there exist infinitely many $m$ such that $D\divides \ell$. Since $$ x_m=\frac{1}{2}\left((x_1+y_1{\sqrt {D}})^m+(x_1-y_1{\sqrt {D}})^m\right) \equiv x_1^m \pmod D, $$ and $$ y_m=\frac{1}{2{\sqrt {D}}}\left((x_1+y_1{\sqrt {D}})^m- (x_1-y_1{\sqrt {D}})^m\right)\equiv mx_1^{m-1}y_1\pmod D, $$ the relation $D\divides (uy_m+x_m)$ is equivalent to $D \divides x_1^{m-1}(umy_1+x_1)$. Since $D$ and $x_1$ are coprime (in light of (\ref{eq:ajouteq})), the above divisibility relation holds if and only if $muy_1\equiv -x_1 \pmod D$. Since both $u$ and $y_1$ are coprime to $D$, it follows that their product is invertible modulo $D$. Hence, if $m\equiv -x_1(uy_1)^{-1} \pmod D$, then $$ n=ux_m+Dy_m $$ has the property that $n^2+k$ is powerful. This completes the proof of the proposition. \end{proof} It now remains to show that for most positive integers $k$ one can choose integers $y_1$ and $d$ such that the conditions from Proposition \ref{prop:alg} are fulfilled. It is clear that for the purpose of making $n^2+k$ powerful, we may assume that $k$ is squarefree. Indeed, if $p^2\divides k$, we may then take $n=pn'$ and note that $$ n^2+k=p^2(n'^2+(k/p^2)), $$ so we may replace $k$ by $k/p^2$. \begin{theorem} \label{thm:anal} The set of squarefree positive integers $k$ for which there exist positive integers $y_1$ and $d\divides ky_1^2+1$ such that the conditions of Proposition \ref{prop:alg} are satisfied is of density 1. \end {theorem} \begin{proof} We let $x$ be a large positive real number and we assume that $k\le x$ is a positive integer. We choose $y_1=12$. \medskip The number $d$ will always be a prime number in a certain arithmetical progression modulo $144$, as follows. If $\gcd(k,6)=1$, we then take $d\equiv 1\pmod {144}$. If $\gcd(k,6)=2$, then $d\equiv 91\pmod {144}$. If $\gcd(k,6)=3$, we put $d\equiv 65\pmod {144}$, and finally if $6\divides k$, we then put $d\equiv 11\pmod {144}$. \medskip We first show that $y_1$ and $D$ are coprime, from which it will follow that $6$ and $D$ are coprime. If $\gcd(k,6)=1$, then since $d\equiv 1 \pmod {144}$, we get that $(144k+1)/d\equiv 1\pmod {144}$. Hence, $(144k+1)/d-d\equiv 0\pmod {144}$, which shows that $6\divides u$. Since $k$ is coprime to $6$, we get that $6$ is coprime to $D$. If $\gcd(k,6)=2$, then $d\equiv 91\pmod {144}$. In particular, $d\equiv 11\pmod {16}$ and $d\equiv 1\pmod 9$. Hence, $(144k+1)/d\equiv 3\pmod {16}$ and $(144k+1)/d\equiv 1\pmod 9$. Thus, $(144k+1)/d-d$ is congruent to $8$ modulo $16$ and to $0$ modulo $9$. Hence, $u$ is an odd multiple of $3$. Since $2$ divides $k$ but $3$ doesn't, we get that $6$ is coprime to $D$. It is easily seen that the other two cases, namely $\gcd(k,6)=3$ and $\gcd(k,6)=6$, can be treated similarly. Moreover, since $\mbox{gcd}(u^2+k,12)=\mbox{gcd}(D,y)=1$ there is no prime $p\in\{2,3\}$ such that $p\divides \gcd(k,u)$. \medskip Thus, it remains to show that for all positive integers $k\le x$ except $o(x)$ of them such a prime $d$ can be chosen in such a way that there is no prime $p>3$ dividing both $u$ and $k$. Note that if $p>3$ divides both $u$ and $k$, then $(144k+1)/d\equiv d\pmod p$, so that $144k+1\equiv d^2\pmod p$, in which case $d^2\equiv 1\pmod p$. Thus, $d\equiv \pm 1\pmod p$. We can reverse the argument to show that if $d\equiv \pm 1 \pmod p$, then $p \divides 2y_1 u$ and $p \divides k$. Since $p>3$ and the largest prime factor of $y_1$ is $3$, the condition $d\equiv \pm 1 \pmod p$ guarantees that $p \divides \gcd(u,k)$. \medskip For coprime positive integers $a,~b$ we write $$ S(x;a,b)=\sum_{p\equiv \fmod{a} {b}}\frac{1}{p}-\frac{\log_2 x}{\phi(b)}. $$ A result of Pomerance (see Theorem 1 and Remark 1 in \cite{Pom}) shows that, uniformly for all $ax$. Write $144k+1=dm$, and note that $m\le 288 x/d<288 p\ll p$. Since $p \divides k$ and $d\equiv \pm 1\pmod p$, we get that $m\equiv \pm 1\pmod p$. Fix $m$. Then $k/p$ is in a certain residue class modulo $m$ depending on $p$. Write $k/p=v+m\ell$. Then $$ dm=144p(k/p)+1=(144pv+1)+144pm\ell, $$ so that $$ d=w+144p\ell, $$ where $w=(144pv+1)/m$. Furthermore, $d\le 288 x/m$. Hence, by a result of Montgomery and Vaughan \cite{MV}, the number of such primes $d$ does not exceed \begin{equation} \label{eq:spe} \frac{4\cdot 144 x}{m\phi(144p)\log(288 x/(mp))}\ll \frac{x}{mp\log x}, \end{equation} where we used the fact that $m\le 288p \le 288 x^{1/3}$, and therefore $$ \frac{288x}{mp}\gg x^{1/3}. $$ Summing up inequality (\ref{eq:spe}) over all the possible values of $m\le 288 p\le 288 x^{1/3}$, and then afterwards over all $p\in [y,z]$, we get that the number of such $k$'s is $$ \ll \frac{x}{\log x} \sum_{y\le p}\frac{1}{p}\sum_{\substack{m\le x \\ m \,\equiv \, \pm \fmod{1} {p}}}\frac{1}{m} \ll x\sum_{y\le p}\frac{1}{p^2}\ll \frac{x}{y\log y}=o(x).$$ \medskip From now on, we consider only those $k$ such that if $d\equiv a\pmod b$ is a prime factor of $144k+1$, with the pair $(a,b)$ being the appropriate one depending on the value of $\gcd(k,6)$, then there exists a prime $p\in [5,y]\cup [x^{1/3},x]$ such that $p \divides \gcd(k,u)$. First observe that $k$ has at most 3 prime factors in $[x^{1/3},x]$. Moreover, for each prime $p>x^{1/3}$, there are at most $3$ values of $d$ such that $d\equiv \pm 1\pmod p$. Indeed, if there were 4 or more, let $d_1,~d_2$, $d_3$ and $d_4$ be 4 of them. We would then have $$ 144x+1\ge 144k+1\ge d_1d_2d_3d_4\ge (x^{1/3}-1)^4, $$ which is impossible for large $x$. Hence, there are at most $9$ values of $d$ which might be congruent to $\pm 1$ modulo some prime factor $p>x^{1/3}$ of $k$. Since we have $(1+o(1)){\displaystyle{\frac{\log_2 x}{\phi(b)}}}$ such primes $d$, it follows that we also have $(1+o(1)){\displaystyle{\frac{\log_2 x}{\phi(b)}}}$ such prime factors $d$ of $144k+1$ with the property that each of them is congruent to $\pm 1$ modulo a prime factor $p$ of $k$ in the interval $[5,y]$. We apply Tur\'an's inequality from \cite{Tur} again to conclude that all $k\le x$ have at most $1.5\log_2 y<2\log_4 x$ prime factors $p(\log_2 x)^{1/3}$$ such primes $d$ which furthermore are congruent to either $1$ or $-1$ modulo $p$ for the {\bf same} prime $p>(\log_3 x)/2$. \medskip We now count how many such $k$'s can there can be. Because of the above argument, we can write $144k+1=d_1d_2\cdots d_\mu Q< 288x$ (for some positive integer $Q$), where each $d_j\equiv \pm 1\pmod p$. Thus, the number of such $k$'s is at most \begin{eqnarray*} \sum_{p>(\log_3 x)/2}\frac{288x}{\mu!}\left(\sum_{\substack{d\le x\\ d \, \equiv \, \fmod{A} {B}\\ d\, \equiv \, \pm \fmod{1} {p}}}\frac{1}{d}\right)^\mu &\ll & x\sum_{p>(\log_3 x)/2}\left(\frac{2e\log_2 x+O(1)} {\mu\phi(B)(p-1)}\right)^\mu\\ &\ll & x\sum_{p>(\log_3 x)/2}\left(\frac{O(\log_4 x)}{p} \right)^{(\log_2 x)^{1/3}}\\ & = & o(x), \end{eqnarray*} which completes the proof of Theorem 3. \end{proof} \section{Comments and Numerical Results} Although we proved that $n^2+k$ is powerful for infinitely many $n$'s only for most integers $k$, we do conjecture that this is actually true for all integers $k$. Indeed, fixing a squarefree integer $k$, the probability that $n^2+k$ is powerful is of the order $\frac{1}{\sqrt{n^2+k}}\approx \frac{1}{n}$ for large $n$. This means that we should expect that \begin{equation}\label{eq:predict} \#\{n\le x: n^2+k \mbox{ is powerful}\} \sim\sum_{n\le x}\frac{1}{n}\sim \log x\rightarrow \infty \quad \mbox{as }x\to \infty \end{equation} for any squarefree $k$. From our proof it follows indeed that if $\#\{n:n^2+k \mbox{ is powerful}\}>1$, then $\#\{n\le x: n^2+k \mbox{ is powerful}\}\gg \log x$. \medskip Table 1 (resp. Table 2) provides, for each integer $1\le k \le 50$, the smallest known value of $n$ for which $n^2+k$ (resp. $n^2-k$) is a powerful number without being a perfect square. These values of $n$ were obtained by finding the minimal solution of $x^2-Dy^2=\pm k$ by considering various cubefull $D$'s. Those $n>10^9$ may not be the smallest $n$ for which $n^2\pm k$ is powerful. \medskip Given three integers $a,b,c$, one could ask if the polynomial $a n^2+bn+c$ is powerful for infinitely many integers $n$. Assuming that $a n^2+bn+c$ is a powerful number which is not a square, we can then write $a n^2+bn+c=Dm^2$ with $D>1$ squarefree and $D\divides m$. We then have $$ n=\frac{-b\pm \sqrt{4aDm^2+b^2-4ac}}{2a}. $$ Since $n$ is an integer, there exists an integer $y$ such that $4aDm^2+b^2-4ac=y^2,$ or, equivalently, $y^2-aD(2m)^2=b^2-4ac$ with $y\equiv \pm b \pmod{2a}$. But then the existence of one solution implies the existence of infinitely many. On the other hand, we also get that if there is an infinity of integers $y$ for which $y^2-b^2+4ac=Dx^2$ where $D>1$ is squarefree and $2aD \divides x$, then there exist infinitely many $n$'s for which $a n^2+bn+c$ is a powerful number. \vskip 15pt The prediction (\ref{eq:predict}) may at first seem at odd with the fact that some of the smallest $n$'s obtained in Tables 1 and 2 are huge. However, the statement ``$n^2+k$ is powerful'' is equivalent to ``$n^2+k=dm^2$ with $d$ squarefree and $d\divides m$''. Now for any fixed $d$, this last equation is a generalized Pell equation. While a solution may not exist for some values of $d$, when it does for a particular $d$, it is well known that the smallest solution can be surprisingly large. When solutions exist, it is still possible that none of them will be such that $d \divides m$. The size of the smallest solution such that $d \divides m$ can also be quite large. There are thus three possible reasons for the huge value of the smallest solution: a large value of $d$, a large value of the smallest solution to $n^2+k=dm^2$ or a large value of the smallest solution such that $d \divides m$. We investigated this in Table 3, where $n=n_0$ is the smallest solution to $n^2+k=dm^2$ not taking into account the restriction $d \divides m$. It turns out that the surprisingly large values of the smallest $n$ in Table 1 are not due to a very large value of $d$ but rather to a large value of $n_0$ (see for instance $k=33$), or to the large size of the smallest solution $n_0$ for which $d \divides m$ (see for instance $k=17$). \centerline{\bf Table 1} \vskip 10pt \begin{small} \noindent \begin{tabular}{|c|c|c|}\hline $k$ & $n$ & $n^2+k$ \\ \hline 1 & 682 & $5^3\cdot 61^2$ \\ 2 & 5 & $3^3$ \\ 3 & 37 & $2^2\cdot 7^3$ \\ 4 & 11 & $5^3 $ \\ 5 &1879706 & $3^5 \cdot 7^2 \cdot 23^3 \cdot 29^3$ \\ 6 & 463 & $5^4\cdot 7^3$\\ 7 & 11 & $2^7$ \\ 8 & 10 & $2^2\cdot 3^3$ \\ 9 & 2046 & $3^2\cdot 5^3\cdot 61^2$ \\ 10 & 341881 & $11^3\cdot 9371^2$\\ 11 & 31 & $2^2\cdot 3^5$ \\ 12 & 74 & $2^4 \cdot 7^3$ \\ 13 & 70 & $17^3$ \\ 14 & 5519 & $3^3\cdot 5^5\cdot 19^2$ \\ 15 & 793 & $2^7\cdot 17^3$ \\ 16 & 22 & $2^2\cdot 5^3$ \\ 17 & $n_{17}$ & $f_{17}$ \\ 18 & 57 & $3^3\cdot 11^2$ \\ 19 & 559 & $2^2\cdot 5^7$ \\ 20 & 338 & $2^3\cdot 3^3 \cdot 23^2$ \\ 21 & $n_{21}$ & $f_{21}$ \\ 22 & 503259461 & $47^3\cdot 491^2\cdot 3181^2$ \\ 23 & 45 & $2^{11}$ \\ 24 & 926 & $2^2\cdot 5^4\cdot 7^3$ \\ 25 & 190 & $5^3\cdot 17^2$ \\ \hline \end{tabular} \quad \begin{tabular}{|c|c|c|}\hline $k$ & $n$ & $n^2+k$ \\ \hline 26 & 109 & $3^5\cdot 7^2$ \\ 27 & 36 & $3^3\cdot 7^2 $ \\ 28 & 62 & $2^5\cdot 11^2$ \\ 29 & 436 & $3^2\cdot 5^3\cdot 13^2$ \\ 30 & 832836278711 & $31^2 \cdot 59^2 \cdot 67^2 \cdot 79^3 \cdot 9679^2$ \\ 31 & 63 & $2^5\cdot 5^3$ \\ 32 & 88 & $2^5\cdot 3^5$ \\ 33 & $n_{33}$ & $f_{33}$ \\ 34 & 7037029 & $5^5 \cdot 7^5\cdot 971^2$ \\ 35 & 36& $11^3$ \\ 36 & 33 & $3^2\cdot 5^3$ \\ 37 & $n_{37}$ & $f_{37}$ \\ 38 & 5945 & $3^2\cdot 7^3\cdot 107^2$\\ 39 & 31& $2^3\cdot 5^3$\\ 40 & 52& $2^3\cdot 7^3$ \\ 41 & 78 & $5^3\cdot 7^2$ \\ 42 & 720025& $13^3 \cdot 31^3 \cdot 89^2$ \\ 43 & 22364 & $11^3\cdot 613^2$ \\ 44 & 62 & $2^4\cdot 3^5$ \\ 45 & 96 & $3^3\cdot 7^3$ \\ 46 & 50927 & $5^5\cdot 11^2 \cdot 19^3$ \\ 47 & 39 & $2^5\cdot 7^2$ \\ 48 & 148 & $2^6\cdot 7^3$ \\ 49 & 524 & $5^3\cdot 13^3$ \\ 50 & 1325& $3^5\cdot 5^2\cdot 17^2$ \\ \hline \end{tabular} \vskip 10pt \noindent Here, $n_{17}=1952785824219551870$ with $f_{17}=3^2\cdot 13^3\cdot 367^2 \cdot 7487^2\cdot 5054107013^2$; \noindent $n_{21} = 4580728614212333152148$ with $f_{21}=5^2\cdot 31^2\cdot 37^3 \cdot 41611^2\cdot 3155673955493^2$; \noindent $n_{33}=2451448196948930$ with $f_{33}=7^2 \cdot 17^3 \cdot 29^3 \cdot 31992951041^2$; \noindent $n_{37}=18651116694721032166213875246076$ with $f_{37}=317^3\cdot 10219159057^2\cdot 323370789682598407^2$. \end{small} \vskip 20pt \centerline{\bf Table 2} \vskip 10pt \begin{small} \noindent \begin{tabular}{|c|c|c|}\hline $k$ & $n$ & $n^2-k$ \\ \hline 1 & 3 & $2^3$ \\ 2 & 11427 & $7^3 \cdot 617^2$ \\ 3 & $n_3$ & $f_3$ \\ 4 & 6 & $2^5$ \\ 5 & 73 & $2^2\cdot 11^3$ \\ 6 & 62531004125 & $19^3\cdot 14831^2\cdot 50909^2$ \\ 7 & $n_7$ & $f_7$ \\ 8 & 20 & $2^3\cdot 7^2$ \\ 9 & 15 & $2^3 \cdot 3^3$ \\ 10 & $n_{10}$ & $f_{10}$ \\ 11 & 56 & $5^5$ \\ 12 & 47 & $13^3$ \\ 13 & 16 & $3^5$ \\ 14 & 33017 & $5^2\cdot 11^3 \cdot 181^2$ \\ 15 & 1138 & $109^3$ \\ 16 & 68 & $2^9\cdot 3^2$ \\ 17 & 23 & $2^9$ \\ 18 & 19 & $7^3$ \\ 19 & 762488 & $3^2\cdot 5^3 \cdot 127^2 \cdot 179^2$ \\ 20 & 146 & $2^4\cdot 11^3$ \\ 21 & 1552808& $43^3\cdot 5507^2$ \\ 22 & 47 & $3^7$ \\ 23 & 6234 & $7^2\cdot 13^3 \cdot 19^2$ \\ 24 & 32 & $2^3 \cdot 5^3$ \\ 25 & 45 & $2^4\cdot 5^3$ \\ \hline \end{tabular} \quad \begin{tabular}{|c|c|c|}\hline $k$ & $n$ & $n^2-k$ \\ \hline 26 & 2537 & $23^5$ \\ 27 & 51700 & $13^3\cdot 1103^2 $ \\ 28 & 54 & $2^3 \cdot 19^2$ \\ 29 & 426 & $7^3 \cdot 23^2$ \\ 30 & 83 & $19^3$ \\ 31 & 34 & $3^2\cdot 5^3$ \\ 32 & 40 & $2^5\cdot 7^2$ \\ 33 & 3601 & $2^8 \cdot 37^3$ \\ 34 & 948281 & $3^6\cdot 47^3 \cdot 109^2$ \\ 35 & 531783519104& $29^3 \cdot 997^2 \cdot 3415409^2$ \\ 36 & 42 & $2^6\cdot 3^3$ \\ 37 & 73 & $2^2\cdot 3^3 \cdot 7^2$ \\ 38 & 16493 & $11^2\cdot 131^3$ \\ 39 & $n_{39}$ & $f_{39}$ \\ 40 & 632 & $2^3\cdot 3^3 \cdot 43^2$ \\ 41 &71 & $ 2^3\cdot 5^4$ \\ 42 & 691888331& $13^2\cdot 79^3\cdot 75797^2$ \\ 43 & 5016 & $13^2 \cdot 53^3$ \\ 44 & 112 & $2^2\cdot 5^5$ \\ 45 & 219 & $2^2\cdot 3^2 \cdot 11^3$ \\ 46 & 847 & $3^3\cdot 163^2$ \\ 47 & 180190 & $53^3 \cdot 467^2$ \\ 48 & 94 & $2^2 \cdot 13^3$ \\ 49 & 56 & $3^2 \cdot 7^3$ \\ 50 & 57135 & $ 5^2\cdot 7^3 \cdot 617^2$ \\ \hline \end{tabular} \vskip 10pt \noindent Here, $n_3=15503069909027$ with $f_3=13^3\cdot 239^2 \cdot 64866401293^2$; \noindent $n_7=85227106679780$ with $f_7=3^3 \cdot 59^3 \cdot 36192438539^2$; \noindent $n_{10}=71457130044805582612325294634331$ with $f_{10}=3^3 \cdot 13^3\cdot 43^2\cdot 6823075915494777091540353511^2$; \noindent $n_{39}=82716851195974$ with $f_{39}=7^2\cdot 373^3\cdot 29287^2\cdot 56009^2$. \end{small} \section{Acknowledgments} The first author was partially supported by a grant from NSERC, while the third author was supported by projects SEP-CONACYT 37259-E and 37260-E. \newpage \centerline{\bf Table 3} \vskip 10pt \begin{center} \begin{small} \noindent \begin{tabular}{|c|c|c|}\hline $k$ & $d$ & $n_0$ \\ \hline 1 & 5 & 2 \\ 2 & 3 & $2$ \\ 3 & 7 & 2 \\ 4 & 5 & 1 \\ 5 & $3\cdot 23 \cdot 29$ & 26258 \\ 6 & 7 & 1\\ 7 & 2 & 1 \\ 8 & 3 & 2 \\ 9 & 5 & 6 \\ 10 & 11 & 1\\ 11 & 3 & 1 \\ 12 & 7 & 4 \\ 13 & 17 & 2 \\ 14 & 15 & 1\\ 15 & 34 & 11 \\ 16 & 5 & 2 \\ 17 & 13 & 10 \\ 18 & 3 & 3 \\ 19 & 5 & 1\\ 20 & 6 & $2$ \\ 21 & 37 & 4 \\ 22 & 47 & $5$ \\ 23 & 2 & 3 \\ 24 & 7 & 2 \\ 25 & 5 & 10\\ \hline \end{tabular} \quad \begin{tabular}{|c|c|c|}\hline $k$ & $d$ & $n_0$ \\ \hline 26 & 3 & 1 \\ 27 & 3 & 9 \\ 28 & 2 & 2 \\ 29 & 5 & 4 \\ 30 & 79 & 7 \\ 31 & 10 & 3 \\ 32 & 6 & 8 \\ 33 & $17\cdot 29$ & 1310 \\ 34 & 35 & 1 \\ 35 & 11& 3 \\ 36 & 5 & 3 \\ 37 & 317 & 61016 \\ 38 & 7 & 5\\ 39 & 10 & 1\\ 40 & 14 & 4 \\ 41 & 5 & 2 \\ 42 & $31\cdot 13$ & 19 \\ 43 & 11 & 1 \\ 44 & 3 & 2\\ 45 & 21 & 12 \\ 46 & 95 & 7 \\ 47 & 2 & 5 \\ 48 & 7 & 8 \\ 49 & 65 & 4 \\ 50 & 3& 5\\ \hline \end{tabular} \vskip 10pt \end{small} \end{center} \vskip 30pt \begin{thebibliography}{9} \bibitem{kn:mollinwalsh} R. A.\,Mollin and P. G.\,Walsh, Proper differences of nonsquare powerful numbers, {\it C. R. Math. Rep. Acad. Sci. Canada} {\bf 10} (1988), no.\ 2, 71--76. \bibitem{MV} H. L.\,Montgomery and R. C.\,Vaughan, The large sieve, {\it Mathematika\/} {\bf 20} (1973), 119--134. \bibitem{Pom} C.\,Pomerance, On the distribution of amicable numbers, {\it J. reine angew. Math.\/}, {\bf 293/294} (1977), 217--222. \bibitem{rob} J. P.\,Robertson, Solving the generalized Pell equation $x^2-Dy^2=N$, \hfill \newline \href{http://www.hometown.aol.com/jpr2718/pell.pdf}{\tt http://www.hometown.aol.com/jpr2718/pell.pdf}. \bibitem{Tur} P. Tur{\'a}n, Uber einige Verallgemeinerungen eines Satzes von Hardy und Ramanujan, {\it J. London Math. Soc.\/}, {\bf 11} (1936), 125--133. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 11A05; Secondary 11N25. \noindent \emph{Keywords: } powerful numbers, generalized Pell equation. \bigskip \hrule \bigskip \noindent (Concerned with sequence \seqnum{A001694}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received October 27 2010; revised version received February 22 2011. Published in {\it Journal of Integer Sequences}, March 25 2011. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}