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.

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

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.

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