We use the function jacobi
to compute the Jacobi symbols for the given numbers.
from algorithms.modular import jacobi
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
-1
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
1
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
-1