# Computing Jacobi symbols¶

We use the function jacobi to compute the Jacobi symbols for the given numbers.

In [1]:
from algorithms.modular import jacobi

In [3]:
jacobi(7411, 9283, trace=True)

7411 9283 1
9283 mod 8 = 3
7411 mod 4 = 3
9283 mod 4 = 3
9283 7411 -1
1872 7411 -1
7411 mod 8 = 3
936 7411 1
468 7411 -1
234 7411 1
117 7411 -1
117 mod 4 = 1
7411 mod 4 = 3
7411 117 -1
40 117 -1
117 mod 8 = 5
20 117 1
10 117 -1
5 117 1
5 mod 4 = 1
117 mod 4 = 1
117 5 1
2 5 1
5 mod 8 = 5
1 5 -1

Out[3]:
-1
In [4]:
jacobi(20964, 1987, trace=True)

1094 1987 1
1987 mod 8 = 3
547 1987 -1
547 mod 4 = 3
1987 mod 4 = 3
1987 547 1
346 547 1
547 mod 8 = 3
173 547 -1
173 mod 4 = 1
547 mod 4 = 3
547 173 -1
28 173 -1
173 mod 8 = 5
14 173 1
7 173 -1
7 mod 4 = 3
173 mod 4 = 1
173 7 -1
5 7 -1
7 mod 8 = 7
5 mod 4 = 1
7 mod 4 = 3
7 5 -1
2 5 -1
5 mod 8 = 5
1 5 1

Out[4]:
1
In [5]:
jacobi(1234567, 11111111, trace=True)

1234567 11111111 1
11111111 mod 8 = 7
1234567 mod 4 = 3
11111111 mod 4 = 3
11111111 1234567 -1
8 1234567 -1
1234567 mod 8 = 7
4 1234567 -1
2 1234567 -1
1 1234567 -1

Out[5]:
-1