1

I'm trying to solve a system of the type

$a^2 \mod n \equiv b\\ b^2 \mod n \equiv c\\ c^2 \mod n \equiv d\\ ...$

Where $n = p q$ for some primes $p$ and $q$. I know how to solve these systems when the unknown is $a$, but here the unknown is $n$. How would I go about solving such a system? I am not sure where to begin.

I tried writing it out as $a^2 - b = ipq$ for some integer $i$, and then factoring $a^2-b$, and repeating for each equation, and then intersecting the resulting solution sets. The problem is that the numbers involved are way too large for factorization to be practical.

Sam
  • 13

1 Answers1

1

Hint $\rm\ n\mid a^2\!-\!b, b^2\!-\!c, c^2\!-\!d\iff n\mid gcd(a^2\!-\!b, b^2\!-\!c, c^2\!-\!d).\:$ The solutions arise from factoring the gcd.

Math Gems
  • 19,574