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