# Quadratic congruence modulo composite number

I am trying for a given N to find the largest a ( $$1 \leq a < N$$) such that

$$a^2\equiv a\pmod N$$

It doesn't need to be a direct formula, I can use some programming too.
N can be no bigger than 10 million.

I know that for N prime or N power of prime, the only such $$a$$ is $$a = 1$$.
That I was able to easily prove (because it is easy to prove).

So... how can I go on and try to solve this for a composite N?

I studied some number theory but this was long ago.
Do I need to use Legendre symbol or Jacobi symbol or something?

Everywhere on the web, I read only how one can solve quadratic congruences modulo $$N=p$$ or at most $$N=p^m$$ (where $$p$$ is prime) but I do not find a good description (full algorithm) on how to go on from there and solve for any composite N. Any hints or references about this?

I was also able to find the first several answers but I don't see any obvious pattern.

    N ---> a
2 ---> 1
3 ---> 1
4 ---> 1
5 ---> 1
6 ---> 4
7 ---> 1
8 ---> 1
9 ---> 1
10 ---> 6
11 ---> 1
12 ---> 9
13 ---> 1
14 ---> 8
15 ---> 10
16 ---> 1
17 ---> 1
18 ---> 10
19 ---> 1
20 ---> 16
21 ---> 15
22 ---> 12
23 ---> 1
24 ---> 16
25 ---> 1
26 ---> 14
27 ---> 1
28 ---> 21
29 ---> 1
30 ---> 25
31 ---> 1
32 ---> 1
33 ---> 22
34 ---> 18
35 ---> 21
36 ---> 28
37 ---> 1
38 ---> 20
39 ---> 27
40 ---> 25
41 ---> 1
42 ---> 36
43 ---> 1
44 ---> 33
45 ---> 36
46 ---> 24
47 ---> 1
48 ---> 33
49 ---> 1
50 ---> 26

• Do you know the Chinese Remainder Theorem? Note that $a^2=a \mod\, N$ means $N|a(a-1)$. Jan 21, 2019 at 21:59
• @Mindlack I had been using it in the past, I kind of know it, yes. I can refresh my knowledge about it quickly. Jan 21, 2019 at 22:40

Given that $$N\leq10^7$$, you can easily factor $$N$$ into a product of prime powers $$N=\prod_{i=1}^m p_i^{n_i}$$, and you will have $$m\leq8$$. By the Chinese remainder theorem you have $$a^2\equiv a\pmod{N}$$ if and only if $$a^2\equiv a\pmod{p_i^{n_i}},$$ for each $$1\leq i\leq m$$. As you note, for each $$i$$ the only solutions are $$a\equiv0,1\pmod{p_i^{n_i}}$$. This yields $$2^m$$ solutions to $$a^2\equiv a\pmod{N}.$$ You can find them all by first solving for each $$1\leq i\leq m$$ the simultaneous congruences $$a_i\equiv1\pmod{p_i^{n_i}} \qquad\text{ and }\qquad a_i\equiv0\pmod{p_j^{n_j}}\ \text{ for all }\ j\neq i,$$ which is equivalent computing the inverse of $$\prod_{j\neq i}p_j^{n_j}$$ mod $$p_i^{n_i}$$. Next compute all subset sums of $$\{a_1,\ldots,a_m\}$$ mod $$N$$, and take the largest one.
• Thanks a lot. But I have $1 \leq a$. Does that mean that from the multiple congruences (mod $p_i^{n_i}$), after using CRT, I get just 1 solution modulo N? Jan 21, 2019 at 22:36
• No, you get precisely $2^m-1$ solutions mod $N$, two branches for each choice of solution mod $p_i^{n_i}$. Only the trivial solution $a=0$, corresponding to the empty subset sum, is not within your range. Jan 21, 2019 at 22:36
• The CRT gives you an isomorphism $$\Bbb{Z}/N\Bbb{Z}\cong\prod_{i=1}^m\Bbb{Z}/p_i^{n_i}\Bbb{Z}.$$ On the right hand side, the solutions to $a^2=a$ are precisely the $m$-tuples consisting of all $0$'s and $1$'s. For each $i$, the solution to the simultaneous congruences I describe yields the $m$-tuple with $1$ in the $i$-th place and $0$'s everywhere else, loosely speaking the $i$-th basis vector. So taking sums of these $m$ basis vectors yields all solutions to $a^2=a$. I suggest to first lift the basis vectors to $\Bbb{Z}/N\Bbb{Z}$, and then compute the sums. Jan 23, 2019 at 10:18