$N = pq$ is the product of two primes.
If $N\equiv 1\pmod 4$, does then follow that $p\equiv q\equiv 1\pmod 4$ ?
Asked
Active
Viewed 41 times
0
-
$3\times 7 = 21$ - not too hard to check a few values... – Joffan May 20 '15 at 17:34
1 Answers
0
No, it doesn't. For $p\equiv q\equiv 3\pmod 4$, $pq\equiv 9\equiv 1\pmod 4$.
Since $p,q\equiv 1,2,3\pmod 4$, one has$$pq\equiv 1\pmod 4\iff p\equiv q\equiv 1\ \ \text{or}\ \ p\equiv q\equiv 3\pmod 4.$$
mathlove
- 139,939
-
Can you without factoring find out if p = q = 1 mod 4 or p = q = 3 mod 4? – testboy May 20 '15 at 17:42
-
-
@testboy: I do not know a computationally efficient way for very large $N$. Interesting question! – André Nicolas May 20 '15 at 17:49
-
@testboy: Ah, sorry I misunderstood what you meant. I think it's difficult... All I can say is that p=q=1 or p=q=3. – mathlove May 20 '15 at 17:53
-
is this a general rule that if: p = k mod h and q = g mod h is then pq = gk mod h – testboy May 20 '15 at 18:10
-
@testboy: Yes, it is. Proof : Since there exist integers $a,b$ such that $p=ha+k,q=hb+g$, one has $pq=(ha+k)(hb+g)=h(hab+ag+kb)+gk\equiv gk\pmod h$. – mathlove May 20 '15 at 18:23