Solve $x^2 \equiv 1 \pmod{30}$ and generalize.

Question

This was one of the questions in a Olympiad number theory course. I used brute force with the CRT: x is odd, not divisible by 3 and its square leaves remainder 1 mod 5 (therefore $x \equiv \pm 1 \pmod 5$). So $x \equiv \pm 1 \pmod{30}$ or $x \equiv \pm 11 \pmod{30}$ . As it can be noted, this is extremely specific and, therefore, a little bit ugly.

How do I generalize this problem for an arbitrary $n$? For example, taking $n = 24$, we have that $5^2 \equiv 1 \pmod n$. So there must be a nontrivial pattern. How do I generalize it?

Answer 1

HINT: write $$(x-1)(x+1)\equiv 0 \mod 30$$

Answer 2

Note: This method works only for primes $n$

Let $0<a<b<n$ such that $a^2 \equiv b^2 (\mod n)$. Then, we have $(b-a)(a+b)\equiv 0 \mod 30$. Since $a<b<n$ and $n$ is a prime, $b-a$ cannot divide $n$. Thus we must have $$(a+b)\equiv 0 \mod 30\Rightarrow a \equiv -b \mod n$$

This means $b=n-a$. Thus we can conclude that only $a^2$ and $(n-a)^2$ can have the same remainder when divided by $n$.

Answer 3

Well $x^2 \equiv 1 \mod 30$ so $x^2-1 = (x+1)(x-1) \equiv 0 \mod 30$.

Now the trivial factors of $0$ are $0$ and anything else so $x \pm 1$ will do (and will do for any modulus).

Non trivial are $2k, 15$, $3k,10j$ and $5k,6j$. Now we need two that are different by $2$. As each pair is relatively prime that can be done.

$2k - 15j = \pm 2$ however requires $j$ to be even which is equivalent to $0$ and is a trivial solution.

$3k - 10j = \pm 2$ is soulbe but $3*6 - 10*2 = -2$ so $(x-1)=18; (x+1) = 20; x = 19$ will do and $19^2= 18*20 + 1\equiv 6*2*30 + 1 \mod 30$.

For $5k - 6j =\pm 2$ there is $k=2; j = 2$and $x-1=10; x+1=12$ or $x = 11$ will do and $11^2 = 121 \equiv 1 \mod 30$.

So the solutions are $1,31,19, 11$ or $\pm 1; \pm 11$.

===

In hind sight is probably easier to use that Chinese remainder theorem.

$x^2 \equiv 1\mod 30 \implies x^2 \equiv 1 \mod 2,3,5$

So $(x-1)(x+1) \equiv 0 \mod 2,3,5$. As $2,3,5$ are prime the only solutions are $1$ and $-1\mod 2,3,5$.

If $x \equiv \pm1 \mod 2;x \equiv 1 \mod 3; x\equiv 1 \mod 5 \implies x \equiv 1 \mod 30$ is a solution.

$x \equiv \pm1\mod 2; x\equiv 1 \mod 3; x \equiv -1 \mod 5 \implies x \equiv 19 \mod 30$.

$x \equiv \pm1\mod 2; x\equiv -1 \mod 3; x \equiv 1 \mod 5 \implies x \equiv 11 \mod 30$.

$x \equiv \pm 1\mod 2; x\equiv -1 \mod 3; x\equiv -1\mod 5 \implies x\equiv 29 \mod 30$.

So those are the $4$ answers.

That can be generalized to any square free composite numbers.

====

Putting it all together:

If $n$ is prime then $x^2 \equiv 1 \mod n\implies (x + 1)(x-1)\equiv 0 \mod n$ and for prime $n$ the only solutions are $x \equiv \pm n$.

If $n = p^k$ then $(x-1)(x+1)\equiv 0 \mod p$ so if $x \not \equiv \pm 1$ then $x+1, x-1$ are both powers of $p$. This is only possible if $p = 2$. Only one of $x \pm 1$ is divisible by $2$ so $x\pm 1 \equiv 2$ and $x \mp 1 \equiv 2^{k-1}$. And $2^{k-1} -2 = 2$ so $k = 3$. And $x \equiv 3$.

So if $x^2 \equiv 1 \mod 2^3$ then $x\equiv \pm 1; \pm 3$

Other wise if $x^2 \equiv 1 \mod p^k$ then $x \equiv \pm 1\mod p^k$.

Finally if $x^2 \equiv 1 \mod n =\prod p_i^{a_i}$ then by CRT

$x \equiv \pm 1\mod p_i^{a_i}$ (or $\pm 3 \mod 8$). And by CRT there will a a unique solution to all of the combinations.

So if $x^2 \equiv 1 \mod 360 = 8*9*5$ then

$x \equiv \pm 1, \pm 3 \mod 8; x\equiv \pm 1 \mod 9; x \equiv \pm 1 \mod 5$.

So there are 16 solutions.

Answer 4

It is: $$x^2=30n+1.$$ Obviously, $x=2k+1$.Then: $$2k(k+1)=15n=15\cdot 2m \Rightarrow k(k+1)=15m.$$ There are $4$ cases: $$1) \ k=3p, k+1=5q \Rightarrow 5q-3p=1 \Rightarrow (p,q)=(-2+5t,-1-3t) \Rightarrow x=2k+1=6p+1=30t-11.$$ $$2) \ k=5r, k+1=3s \Rightarrow 3s-5r=1 \Rightarrow (r,s)=(1+3t,2+5t) \Rightarrow x=2k+1=10r+1=30t+11.$$ $$3) \ k=15t \Rightarrow x=2k+1=30t+1.$$ $$4) \ k+1=15t \Rightarrow x=2k+1=30t-1.$$ Hence, the solutions are: $$x=30n\pm 1; 30n\pm 11.$$