I was solving algebras with certain domain and end up with a nice congruence formula, I failed to do some research about how to solve this since I don't know how to describe this problem, so I hope someone could help me out.

Here's the problem:

$$ p^4 \equiv N^2 \space \pmod{4p^2} $$

where all I know is $N$ will be a given integer that is not prime and $p$ is a prime less than $N$.

I am looking for a specific p that satisfy this equation, for example,

$$7^4 \equiv 21^2 \space (mod \space 4(7^2))$$

If more details are desired, please let me know.

Thanks in advance

  • 1
    $\begingroup$ What is your question? $\endgroup$
    – Servaes
    Apr 2 '19 at 23:18
  • $\begingroup$ @Servaes Thanks for reminding me about, just edited it. $\endgroup$
    – PetaGlz
    Apr 2 '19 at 23:24
  • $\begingroup$ is this used in factoring or cryptographic keys ? $\endgroup$
    – user645636
    Apr 3 '19 at 0:22
  • $\begingroup$ @RoddyMacPhee Yes! I'm working on some factoring problems and get myself stuck in here.. $\endgroup$
    – PetaGlz
    Apr 3 '19 at 0:26
  • $\begingroup$ For a class? or other purposes. $\endgroup$
    – user645636
    Apr 3 '19 at 0:30

The equation you're dealing with is

$$p^4 \equiv N^2 \pmod{4p^2} \tag{1}\label{eq1}$$

Moving $N^2$ to the left and factoring gives that

$$\left(p^2 - N\right)\left(p^2 + N\right) \equiv 0 \pmod{4p^2} \tag{2}\label{eq2}$$

Since $p$ is a prime, it must divide $p^2 - N$ or $p^2 + N$, with both cases requiring that

$$N = kp \tag{3}\label{eq3}$$

for some integer $k$. Thus, \eqref{eq2} becomes

$$p^2\left(p - k\right)\left(p + k\right) \equiv 0 \pmod{4p^2} \tag{4}\label{eq4}$$


$$\left(p - k\right)\left(p + k\right) \equiv 0 \pmod{4} \tag{5}\label{eq5}$$

If $p = 2$, this requires that $k$ be an even integer, while if $p$ is an odd prime, then any odd integer $k$ will work.

In summary, for a given $N$, any of its prime factors $p$ could work, but with the restrictions that if it's $p = 2$, then \eqref{eq1} is satisfied if $N$ is a multiple of $4$, and if it's an odd prime $p$, then \eqref{eq1} is satisfied if $N$ is an odd integer.

  • $\begingroup$ Thanks a lot! I think that makes a lot of sense. $\endgroup$
    – PetaGlz
    Apr 3 '19 at 1:05
  • $\begingroup$ @PetaGlz You are welcome. I'm glad I was able to help. $\endgroup$ Apr 3 '19 at 1:06

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.