4
$\begingroup$

I did some experiment with my Python script to find a number which could divide $n^4$ in this interval ($n^2-n$, $n^2$). I watched the form of prim factors of the numbers in this ($n^2-n$, $n^2$) interval, but I hadn't was any idea for proofing it. Can anyone to help with some start idea to proof that if $n^2-n < k < n^2$ then $k$ can't divide $n^4$.

$\endgroup$
  • $\begingroup$ $n$ doesn't divide $k$. Since $n<k$, there must be a prime number $p$ which divides $k$ but not $n$, thus also not $n^4$, so $k$ cannot divide $n^4$ $\endgroup$ – Pink Panther Mar 28 at 12:28
  • $\begingroup$ @PinkPanther Why does the fact that $n$ does not divide $k$ imply that there is a prime $p$ dividing $k$ but not $n$? After all, $6$ does not divide $3$. $\endgroup$ – lulu Mar 28 at 12:31
  • $\begingroup$ @lulu you have to use the fact that $n<k$, then it should be very straight forward. $\endgroup$ – Pink Panther Mar 28 at 12:32
  • $\begingroup$ @PinkPanther Could you write it out? $12$ does not divide $18$ either... $\endgroup$ – lulu Mar 28 at 12:33
  • $\begingroup$ @lulu you are right. I guess what I wanted to say is that there is a prime power which divides $k$ but not $n$, that is, there exists $p$ and $l$ such that $p^l$ divides $k$ but not $n$.I will write a complete answer in a moment. $\endgroup$ – Pink Panther Mar 28 at 12:37
6
$\begingroup$

Let $0<i<n$ and suppose that $n^2-i$ divides $n^4$. Then, $$ n^4=(n^2-i)(n^2+j)=n^4+(j-i)n^2-i\,j\implies i\,j=(j-i)n^2 $$ for some integer $j$. If $j\le i$, then $$ n^4=(n^2-i)(n^2+j)\le(n^2-i)(n^2+i)=n^4-i^2. $$ Thus, $j>i$. Since $i<n$, it follows that $j>(j-i)n\ge n$. Moreover $$ n\le j=\frac{i\,n^2}{n^2-i}<\frac{i\,n^2}{n^2-n}=\frac{i\,n}{n-1}\implies i>n-1, $$ a contradiction with the fact that $i<n$.

$\endgroup$
  • 1
    $\begingroup$ Thank you for your nice answer, but I can't see one step at this moment: How can we now that $j>i$ ?. And this presumption is used in $(j−i)n>n$ as I see. $\endgroup$ – László Szilágyi Mar 28 at 16:21
  • $\begingroup$ $ij > 0$ and $n^2 > 0$ so if $ij = (j-i)n^2 > 0$ then $j-i > 0$. ...(I suppose it should be points out that $i$ is positive (as $i = n^2 k; n^2 -n < k < n^2$. Ad that that $j > 0$ As if $k < n^2$ then $\frac {n^4}{k} > n^2$ so $n^2 + j = \frac {n^4}{k}$.) $\endgroup$ – fleablood Mar 28 at 17:14
  • $\begingroup$ My answer is along the same lines, and I had deleted it when I saw that, but then I noticed that you claimed that $(j-i)n\gt n$ when it is not clear why $j-i\gt1$. $\endgroup$ – robjohn Mar 28 at 17:28
  • $\begingroup$ @fleablood Why $i*j>0$ is ? $\endgroup$ – László Szilágyi Mar 28 at 18:25
  • $\begingroup$ Why is $i*j > 0$. Seriously? Because $i > 0$ and $j > 0$. And, as I said $i > 0$ because $n^2 > k$ so $i = n^2 -k > 0$ and $j > 0$ because $k < n^2 $ so $n^2 = \frac {n^4}{n^2} < \frac {n^4}k$. So $j = \frac {n^4}k - n^2 > 0$. $\endgroup$ – fleablood Mar 28 at 19:11
3
$\begingroup$

Answer to the Question

Let $k=n^2-a$. Since $n^2-a\mid n^4$ and $$ \frac{n^4}{n^2-a}=n^2+a+\frac{a^2}{n^2-a} $$ we must have $d=\frac{a^2}{n^2-a}\in\mathbb{Z}$. However, since $\color{#C00}{1\le a\le n-1}$ and $\frac{a^2}{n^2-a}$ is increasing in $a$, $$ 0\lt\overbrace{\ \frac1{n^2-1}\ }^{\large\color{#C00}{a=1}}\le d\le\overbrace{\frac{n^2-2n+1}{n^2-n+1}}^{\large\color{#C00}{a=n-1}}\lt1 $$ which is impossible because there is no integer between $0$ and $1$.


Bounding the Greatest Factor of $\boldsymbol{n^4}$ less than $\boldsymbol{n^2}$

Case: $\boldsymbol{d=1}$

Since $n^2=a^2+a$, we have $n-1\lt a\lt n$, which is impossible.

Case: $\boldsymbol{d=2}$

Since $n^2=\frac{a(a+2)}2$, $\sqrt2\,n-1\lt a\lt\sqrt2\,n$. In fact, $2n^2+1=(a+1)^2$. That means that $$ \left(\frac{a+1}n\right)^2=2+\frac1{n^2}\lt\left(\sqrt2+\frac1{2n^2}\right)^2 $$ Which forces $\frac{a+1}n$ to be a continued fraction overestimate of $\sqrt2$ . This gives the first pairs $(n,a)$ to be $$ \{(0,0),(2,2),(12,16),(70,98),(408,576),(2378,3362),(13860,19600)\} $$ The recursion for $n_k$ is $n_k=6n_{k-1}-n_{k-2}$ and $a_k=\left\lfloor\sqrt2\,n\right\rfloor$.

In any case, we have

The largest factor of $n^4$ less than $n^2$ must be less than $n^2-\sqrt2\,n+1$ and there are an infinite number of $n$ so that the largest factor of $n^4$ less than $n^2$ is greater than $n^2-\sqrt2\,n$.

$\endgroup$
  • $\begingroup$ Why $m-k>=1$ is ? $\endgroup$ – László Szilágyi Mar 28 at 18:26
  • $\begingroup$ @LászlóSzilágyi: I have extended the answer to cover that and to free up $k$. $\endgroup$ – robjohn Mar 28 at 19:19
  • $\begingroup$ I would also like to understand your derivation, but now I can see a few letters of error in it and then pleas correct it if you have the time. /: ($b-a=n^2/ab$) and what is role of $k$ $\endgroup$ – László Szilágyi Mar 28 at 21:49
  • $\begingroup$ I changed from $k$ and $m$ to $a$ and $b$ to avoid conflict with $k$ from the question. In the first sentence, it is stated that $k=n^2-a$. Since $n^4=n^4+(b-a)n^2-ab$, we have $(b-a)n^2=ab$. I fixed the typo. $\endgroup$ – robjohn Mar 28 at 22:51
  • $\begingroup$ @LászlóSzilágyi evidently the sharp result is that we can have a factor of $n^4$ as large as $n^2 - \lfloor n \sqrt 2 \rfloor \; , \;$ but no larger. This occurs with integers $x,y > 0,$ $x^2 - 2 y^2 = 1,$ and then $n=2xy.$ $\endgroup$ – Will Jagy Mar 29 at 0:19
2
$\begingroup$

The best examples come from $n=2xy,$ where $x,y>0$ are integers and $x^2 - 2 y^2 = \pm 1 \; . \;$ In these cases we get a factor $m$ of $n^4$ near $n^2 - n \sqrt 2 \; . \; $ When $x^2 - 2 y^2 = 1,$ we get $m = n^2 - 2 x^2.$ When $x^2 - 2 y^2 = -1,$ we get $m = n^2 - 4 y^2.$

jagy@phobeusjunior:~$ ./mse
 n: 2 =  2  m:  2  n^2 - m:  2 =  2
 n: 3 =  3  m:  3  n^2 - m:  6 =  2 3
 n: 4 =  2^2  m:  8  n^2 - m:  8 =  2^3
 n: 6 =  2 3  m:  27  n^2 - m:  9 =  3^2
 n: 10 =  2 5  m:  80  n^2 - m:  20 =  2^2 5
 n: 12 =  2^2 3  m:  128  n^2 - m:  16 =  2^4
 n: 24 =  2^3 3  m:  512  n^2 - m:  64 =  2^6
 n: 30 =  2 3 5  m:  810  n^2 - m:  90 =  2 3^2 5
 n: 60 =  2^2 3 5  m:  3456  n^2 - m:  144 =  2^4 3^2
 n: 70 =  2 5 7  m:  4802  n^2 - m:  98 =  2 7^2
 n: 84 =  2^2 3 7  m:  6912  n^2 - m:  144 =  2^4 3^2
 n: 140 =  2^2 5 7  m:  19208  n^2 - m:  392 =  2^3 7^2
 n: 168 =  2^3 3 7  m:  27783  n^2 - m:  441 =  3^2 7^2
 n: 180 =  2^2 3^2 5  m:  32000  n^2 - m:  400 =  2^4 5^2
 n: 408 =  2^3 3 17  m:  165888  n^2 - m:  576 =  2^6 3^2
 n: 594 =  2 3^3 11  m:  351384  n^2 - m:  1452 =  2^2 3 11^2
 n: 816 =  2^4 3 17  m:  663552  n^2 - m:  2304 =  2^8 3^2
 n: 1170 =  2 3^2 5 13  m:  1366875  n^2 - m:  2025 =  3^4 5^2
 n: 2378 =  2 29 41  m:  5651522  n^2 - m:  3362 =  2 41^2
 n: 3230 =  2 5 17 19  m:  10425680  n^2 - m:  7220 =  2^2 5 19^2
 n: 4756 =  2^2 29 41  m:  22606088  n^2 - m:  13448 =  2^3 41^2
 n: 5880 =  2^3 3 5 7^2  m:  34560000  n^2 - m:  14400 =  2^6 3^2 5^2
 n: 13860 =  2^2 3^2 5 7 11  m:  192080000  n^2 - m:  19600 =  2^4 5^2 7^2
 n: 16296 =  2^3 3 7 97  m:  265531392  n^2 - m:  28224 =  2^6 3^2 7^2
 n: 27720 =  2^3 3^2 5 7 11  m:  768320000  n^2 - m:  78400 =  2^6 5^2 7^2
 n: 42672 =  2^4 3 7 127  m:  1820786688  n^2 - m:  112896 =  2^8 3^2 7^2
 n: 57960 =  2^3 3^2 5 7 23  m:  3359232000  n^2 - m:  129600 =  2^6 3^4 5^2
 n: 58206 =  2 3 89 109  m:  3387795864  n^2 - m:  142572 =  2^2 3 109^2
 n: 80782 =  2 13^2 239  m:  6525617282  n^2 - m:  114242 =  2 239^2
$\endgroup$
  • $\begingroup$ (+1) for the inspiration to prove the maximum. $\endgroup$ – robjohn Mar 29 at 6:20

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.