Regarding the Jacobi symbol, suppose I want to find which positive odd integers that relatively prime to a prime p such as 13 i.e.

$\displaystyle \left( \frac{13}{n} \right) = 1$?

=============

I understand that to do composite integers such as $\displaystyle \left( \frac{10}{n} \right) = \left( \frac{2}{n} \right) \left( \frac{5}{n} \right) = 1$

From here, we want (2/p) = (5/p) = 1 or (2/p) = (5/p) = -1.

$\displaystyle \left( \frac{2}{p} \right) =\begin{cases}

+1&\text{if } p \equiv \pm 1 \pmod{8}\\

-1&\text{if } p \equiv \pm 3 \pmod{8} \end{cases}$

and

$\displaystyle \left( \frac{5}{p} \right) =\begin{cases}

+1&\text{if } p \equiv \pm 1 \pmod{5}\\

-1&\text{if } p \equiv \pm 2 \pmod{5} \end{cases}$

Then by the Chinese Remainder Theorem, then $\displaystyle p \equiv \pm 1 \equiv \pm 3 \equiv \pm 9 \equiv \pm 13 \pmod{40} $

=============

Similarly, how would you solve for big numbers such as 1040 in the simplest way? i.e. which positive odd integers n such that (1040, n) = 1 and (1040/n) = 1?

Thank you for reading. Any help is greatly appreciated.