# solving square congruence with prime

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.

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

Thus,

$$\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.

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