Mathematics Asked by jibber032394 on March 4, 2021

So, I know this is only possible whenever $d$ is a square $pmod{4cdot |n|}$, but can that be simplified any further?

As an example, if I am given that $d=-39$ and $n=500$, this reduces to solving $x^2 equiv -39 pmod{500}$, but how can I find concrete $x$‘s that satisfy the equation? What if the $x$‘s have to be prime?

OK, let's do the example $x^2 equiv -39 mod 500$. $500 = 4 times 5^3 $ so we'll solve it mod $4$ and mod $5^3$, and use the Chinese Remainder Theorem.

$-39 equiv 1 mod 4$, and $x^2 equiv 1 mod 4$ iff $x$ is odd, i.e. $x equiv 1$ or $3 mod 4$.

$-39 equiv 1 mod 5$, and $x^2 equiv 1 mod 5$ iff $x equiv 1$ or $4 mod 5$.

If $x = 1 + 5 y$, $x^2 equiv 1 + 10 y equiv -39 mod 25$ iff $2 y equiv 3 mod 5$ iff $y equiv 1 mod 5$. If $x = 1 + 5 cdot 1 + 5^2 cdot z = 6 + 5^2 cdot z$, $x^2 equiv 6^2 + 2 cdot 6 cdot 5^2 z equiv 36 + 50 z equiv -39 mod 125$ iff $50 z equiv 50 mod 125$ iff $z equiv 1 mod 5$. Thus $x equiv 1 + 5 cdot 1 + 5^2 cdot 1 = 31mod 125$.

Similarly, corresponding to $x equiv 4 equiv -1 mod 5$ we find $x equiv -31 equiv 94 mod 125$.

Now for Chinese Remainder. There are $4$ cases to consider:

- If $x equiv 1 mod 4$ and $x equiv 31 mod 125$, $x equiv 281 mod 500$.
- If $x equiv 1 mod 4$ and $x equiv 94 mod 125$, $x equiv 469 mod 500$.
- If $x equiv 3 mod 4$ and $x equiv 31 mod 125$, $x equiv 31 mod 500$.
- If $x equiv 3 mod 4$ and $x equiv 94 mod 125$, $x equiv 219 mod 500$.

So the solutions mod $500$ are $281, 469, 31$ and $219$.

Each of these four values mod $500$ should correspond to infinitely many primes. The simplest thing to do is to check $281 + 500 k$, $461 + 500 k$, $31 + 500 k$, $219 + 500 k$ for each integer $k$ from $0$ until we find as many primes as we want. As it happens, all but $219$ turn out to be prime for $k=0$, while $219 + 500 = 719$ is prime.

Answered by Robert Israel on March 4, 2021

Get help from others!

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

Recent Answers

- Lex on Does Google Analytics track 404 page responses as valid page views?
- haakon.io on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP