3
$\begingroup$

Given a prime number $p$, I am looking to find the smallest positive integer $k$ such that the following equation $$13 + 4 \cdot k \cdot p^2$$ produces a perfect odd square. All variables are integers. For example, for the prime $43$, $k = 3$. For $p=103$ , it turns out that $k = 1391$. A computer program can solve this for small prime numbers. It is easy to prove that $k$ has to be odd too, which improves the search. But for larger primes, say $p>10^4$, the naive approach of incrementing $k$ untill a suitable value is found just takes a long time.

It is important to mention that not all primes have any solution at all. For those which do have a solution, I am interested in an efficient way for finding it.

Is there any other approach to tackle this? Perhaps one that relates to number theory? Or any other field really which may prove useful.

$\endgroup$
8
  • $\begingroup$ But there may not be such a $k$, right? When $p=5$ if $n^2=13+4k\cdot5^2$ then $3$ is a quadratic residue mod $5$. $\endgroup$
    – saulspatz
    Oct 31, 2020 at 20:28
  • 4
    $\begingroup$ You're trying to solve the congruence $x^2 \equiv 13 \pmod{4p^2}$. Quadratic reciprocity tells you when $x^2 \equiv 13 \pmod{p}$ has a solution (for odd $p$). If you have one, you can lift the exponent to get a solution of $x^2 \equiv 13 \pmod{p^2}$. An odd solution of that gives you a solution of $x^2 \equiv 13 \pmod{4p^2}$. $\endgroup$
    – Daniel Fischer
    Oct 31, 2020 at 20:32
  • $\begingroup$ @saulspatz yes, not all primes admit a solution to this equation $\endgroup$
    – MC From Scratch
    Oct 31, 2020 at 21:42
  • $\begingroup$ @DanielFischer Can you please elaborate on your technique? I can figure which primes admit a solution to this equation. But for those who do, how can I quickly find the actual solution with a method that is more efficient than a naive iteration over $k$? $\endgroup$
    – MC From Scratch
    Oct 31, 2020 at 21:44
  • 2
    $\begingroup$ You want to find a modular square root. For $p \equiv 3 \pmod{4}$ or $p \equiv 5 \pmod{8}$ that's pretty easy. For $p \equiv 1 \pmod{8}$, Tonelli-Shanks or Cipolla are the standard methods. $\endgroup$
    – Daniel Fischer
    Oct 31, 2020 at 21:56

1 Answer 1

Reset to default
0
$\begingroup$

There is one major optimization screaming at me here.

Check each square sequentially for whether or not it is the “odd square” that the formula equals. This will be faster because $n^2$ (for odd $n$) grows faster than the current linear formula dependent on $k$.

Of course you would start with the first square greater than $13 + 4p^2$ since any lower square is impossible.

This method will be faster when $\frac {n^2}{4p^2} > n - \sqrt{4p^2} = n - 2p$.

I do not know whether or not this equation ever works out to being true. However, for sufficiently large $p$ I strongly suspect that iterating through the squares will be faster.

One may note that my formula assumes that every multiple of $p^2$ needs to be as well as every $n^2$. This cancels out as I would divide both sides by $2$. Therefore it is irrelevant.

EDIT:

I thought about this a bit more. For sufficiently small $k$ iterating through squares will be slower (because the growth rate of sequential squares will be smaller than the growth of sequential multiples of $4p^2$). Once $k > 2p^2 - 1$ the growth of sequential squares outpaces the linear growth of your formula. Therefore you should add something in your code to start counting by squares once you reach $k = 2p^2 - 2$. The value of $n$ to start iterating squares would then be $n = 2p^2 - 1$.

This should be about as fast you can get (assuming $k$ exists) other than iterating through odd values of $k$ and $n$.

$\endgroup$
6
  • $\begingroup$ I have thought about this further and I may be able to improve this with a chart of sorts. Basically given any $k$ the next possible number to check will not necessarily be $k + 2$. This has to do with which multiples of $k$ possess remainders when divided by $13$ consistent with squares. $\endgroup$
    – user64742
    Oct 31, 2020 at 21:46
  • $\begingroup$ Prior, to posting this question, I had already tried iterating over the squares rather than values of $k$. It did not seem to provide any major improvement for some reason. But I do agree with the approach in general. I would like to hear more about your approach in the comment though if it looks promising $\endgroup$
    – MC From Scratch
    Oct 31, 2020 at 21:50
  • $\begingroup$ @MCFromScratch so iterating squares will only be faster when $k$ exceeds $2p^2$. Your current examples do not require $k$ to exceed $2p^2$. I am proposing a hybrid. Iterate linearly for small $k$ and then iterate squares if $k$ gets too large. $\endgroup$
    – user64742
    Oct 31, 2020 at 21:55
  • $\begingroup$ @MCFromScratch for the chart I am proposing that each $p$ has a corresponding $x_0$ remainder $26$. The chart will dictate given $x_0$ what integer $b$ to add to $k$ to get the next value to be checked. That value will have an $x_1$ that will dictate the next value $x_2$ and so on and so on. Essentially we will use a secondary counter and a lookup table to decide at any time what value to add to $k$ in your iteration. I will try to get it done soon-ish. $\endgroup$
    – user64742
    Oct 31, 2020 at 21:59
  • $\begingroup$ @MCFromScratch I apologize for the delay. Unfortunately the chart is taking a long time to make (I cannot quite conceive a way to formulaically generate it). I will have to resume working on it tomorrow. $\endgroup$
    – user64742
    Oct 31, 2020 at 23:14

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.