1. ## [SOLVED] Jacobi Symbol

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.

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

=============
I understand that to do composite integers such as $\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.

$\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

$\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 $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.

2. Originally Posted by Paperwings
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.

$\left( \frac{13}{n} \right) = 1$?
If $a,b$ are odd, relatively prime, positive integers, then $(a/b) = (b/a)$ if either $a\text{ or }b\equiv 1(\bmod 4)$ otherwise $(a/b) = - (b/a)$.
Therefore, $(13/n) = (n/13)$.
Thus, for $(n/13) = 1$ we want the squares mod $13$ which are $1,3,4,9,10,12$.
Therefore, $n\equiv \pm 1, \pm 3, \pm 4 (\bmod 13)$.
$n^{(p-1)/2} \equiv 1 \pmod{p} \implies n^{(13-1)/2} \equiv n^6 \equiv 1 \pmod{13}$