1
$\begingroup$

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
$\endgroup$
2
  • $\begingroup$ Do you know the Chinese Remainder Theorem? Note that $a^2=a \mod\, N$ means $N|a(a-1)$. $\endgroup$ – Mindlack Jan 21 '19 at 21:59
  • $\begingroup$ @Mindlack I had been using it in the past, I kind of know it, yes. I can refresh my knowledge about it quickly. $\endgroup$ – peter.petrov Jan 21 '19 at 22:40
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ – peter.petrov Jan 21 '19 at 22:36
  • $\begingroup$ 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. $\endgroup$ – Servaes Jan 21 '19 at 22:36
  • $\begingroup$ "You can find them all by first solving..." I did some research today about CRT. In the general case, I don't think there's any reference to some algorithm like the one you suggest in the part starting with that phrase. Where does all this (the trick with the subsets etc.) come from? $\endgroup$ – peter.petrov Jan 23 '19 at 0:05
  • $\begingroup$ 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. $\endgroup$ – Servaes Jan 23 '19 at 10:18

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.