Find the number $m$ such that $m^2 + 1$ is divisible by $x$ for $x = 474993$
So, I think it will be $m^2+1 \equiv 0$ (mod $474993$), I have no clue how to solve this, any hints would be appreciated. Thank you!
Asked
Active
Viewed 85 times
1
-
1Does this answer your question? Computing modular square roots – Sophie Dec 03 '20 at 15:59
-
2Using $p$ to denote the modulus is misleading, because $474993 = 3^2 \cdot 52777$ is not actually prime... – Seokbin Lee Dec 03 '20 at 16:01
-
4$p=3^2 \cdot 89 \cdot 593$. – Neat Math Dec 03 '20 at 16:02
-
Hello and welcome to math.stackexchange. What is the context? A course in elementary number theory? Is it exam time??? – Hans Engler Dec 03 '20 at 16:02
-
5and $m^2+1\equiv0\pmod{3^2}$ has no solutions – J. W. Tanner Dec 03 '20 at 16:03
-
@HansEngler I'm practicing exercises – Dec 03 '20 at 16:03
1 Answers
2
Hint. There are no solutions to the given equation.
Observe that $474993=3^2\cdot89\cdot593$. Thus, $m^2+1\equiv 0\bmod 474993\implies m^2\equiv-1\bmod 3$ . Yet it is well known that this is impossible.
Dr. Mathva
- 8,621
-
Thank you for your answer! I have a question, how can you factoring a large number? Like you did $474993 = 3^2\cdot89\cdot593$ – Dec 03 '20 at 16:13
-
1There are tools such as this online to factor large numbers. In your case, however, it is easy to see that the number is divisible by $9$ because the sum of its digits is divisible by $9$. So the use of $\bmod 3$ to determine the lack of solutions follows without needing to fully factor the number. – Keith Backman Dec 03 '20 at 16:46
-
Exactly! In this case, it was enough to check that $474993\equiv0\bmod3\iff 4+7+4+9+9+3\equiv 0\bmod 3$ – Dr. Mathva Dec 03 '20 at 16:54