Quadratic congruence modulo composite number

Question

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 just need some hints about this. It doesn't need to be a complete solution.

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

Answer 1

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.