2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ $x^2 \equiv 1 \mod 24; (x -1)(x+1)\equiv 24$ so $(x-1)(x+1) \equiv 0\mod 3,8$ So $x\equiv \pm 1\mod 3$ and $x \equiv \pm 1; \pm 3 \mod 8$. So 8 answers $x \equiv 1\mod 3\equiv 1\mod 8\equiv 1\mod 24$ or $x\equiv 1\mod 3\equiv -1\mod 8\equiv 7\mod 24$ or $x\equiv 1\mod 3\equiv 3\mod 8\equiv 19\mod 24$ or $x\equiv 1\mod 3\equiv -3\mod 8\equiv 13\mod 24$ and the four negatives of those. $\endgroup$ – fleablood Mar 28 '18 at 19:00
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I wrote it like this before and, since $\mathrm{gcd}(x-1, x+1)$ = 2, I concluded that $\frac{x-1}{2} \cdot \frac{x+1}{2} = 15y’$, where the factors on the LHS are coprime, but I couldn’t advance. $\endgroup$ – Lucas Henrique Mar 28 '18 at 17:55
  • $\begingroup$ $\gcd(x-1,x+1) = 2$ what if $x$ is even? Anyway $(x-1)(x+1) \equiv 0$ means $(x-1)(x+1)= k*30$. What are the divisors of $30$? If the divisors are coprime you can find them that are $2$ apart. $\endgroup$ – fleablood Mar 28 '18 at 18:12
  • $\begingroup$ If $x$ is even then both $x-1, x+1$ are odd and then $(x+1)(x-1) = 2(15k)$ is odd. Absurd. $\endgroup$ – Lucas Henrique Mar 28 '18 at 18:35
  • $\begingroup$ Oh, can't argue with that..... $\endgroup$ – fleablood Mar 28 '18 at 18:51
  • $\begingroup$ I didn’t advance at all. Could you help me? $\endgroup$ – Lucas Henrique Mar 28 '18 at 21:55
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Upvoted. But there is a problem: how do we count how many solutions are there? $\endgroup$ – Lucas Henrique Mar 29 '18 at 4:01
  • $\begingroup$ If $n=2^k\prod_{i=1}^m p_i^{a_i}$ is the unique prime factor of $n$ then $x =\equiv \pm 1 \mod p_i^{a_i}$ are $2^m$ systems of equations. Each system has a unique solution. If $k=1$ then $x\equiv 1\mod 2$ is a single equation and there are $2^m$ solutions. If $k=3$ then $x\equiv \pm 1,\pm 3 \mod 8$ our four equations and there are $4*2^m$ solutions. Otherwise $x\equiv \pm 1\mod 2^k$ is two equations and there are $2*2^m$ solutions. So there are $2^i*2^m$ solutions where $m$ is the number of odd primes. $i=2,10$ depending on if the highest power of $2$ dividing $n$ is 3, not 3, or 1 or 0. $\endgroup$ – fleablood Mar 29 '18 at 17:21
  • $\begingroup$ Oh, this can be guaranteed because of the CRY right? $\endgroup$ – Lucas Henrique Mar 29 '18 at 22:08
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ $b-a$ is not necessarily coprime to $n$ so your argument fails. $\endgroup$ – Lucas Henrique Mar 28 '18 at 18:02
  • $\begingroup$ I had this in mind, too. But it didn’t go so well... $\endgroup$ – Lucas Henrique Mar 28 '18 at 18:02
  • 1
    $\begingroup$ @LucasHenrique Ah yes, this method works only for primes... $\endgroup$ – Prathyush Poduval Mar 28 '18 at 18:05
  • $\begingroup$ $11^2 = 4*30 + 1$. $19^2 \equiv 1 \mod 30$> $\endgroup$ – fleablood Mar 28 '18 at 18:13
  • $\begingroup$ @fleablood This is only for prime $n$ $\endgroup$ – Prathyush Poduval Mar 28 '18 at 18:14
0
$\begingroup$

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

$\endgroup$

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.