Definition
For any integer ''a'' and any positive odd integer ''n'', the Jacobi symbol is defined as the product of the Legendre symbols corresponding to the prime factors of ''n'': : where : is the prime factorization of ''n''. The Legendre symbol is defined for all integers ''a'' and all odd primes ''p'' by : Following the normal convention for the empty product, = 1. When the lower argument is an odd prime, the Jacobi symbol is equal to the Legendre symbol.Table of values
The following is a table of values of Jacobi symbol with ''n'' β€ 59, ''k'' β€ 30, ''n'' odd. {, class="wikitable" style="margin-left: auto; margin-right: auto; border: none; text-align: right" ! !1 !2 !3 !4 !5 !6 !7 !8 !9 !10 !11 !12 !13 !14 !15 !16 !17 !18 !19 !20 !21 !22 !23 !24 !25 !26 !27 !28 !29 !30 , - !1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , - !3 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , - !5 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , - !7 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , - !9 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , - !11 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , - !13 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , - !15 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , - !17 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , - !19 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , - !21 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , - !23 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , - !25 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , - !27 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , - !29 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , - !31 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , - !33 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , - !35 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , - !37 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , - !39 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , - !41 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , - !43 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , - !45 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , - !47 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , - !49 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , - !51 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , - !53 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , - !55 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , - !57 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffffcc", 0 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffffcc", 0 , - !59 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1 , style="background:#ccffff", β1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ffccff", 1 , style="background:#ccffff", β1Properties
The following facts, even the reciprocity laws, are straightforward deductions from the definition of the Jacobi symbol and the corresponding properties of the Legendre symbol. The Jacobi symbol is defined only when the upper argument ("numerator") is an integer and the lower argument ("denominator") is a positive odd integer. :1. If ''n'' is (an odd) prime, then the Jacobi symbol is equal to (and written the same as) the corresponding Legendre symbol. :2. If , then :3. If either the top or bottom argument is fixed, the Jacobi symbol is aCalculating the Jacobi symbol
The above formulas lead to an efficient algorithm for calculating the Jacobi symbol, analogous to theImplementation in
Implementation in
Example of calculations
The Legendre symbol is only defined for odd primes ''p''. It obeys the same rules as the Jacobi symbol (i.e., reciprocity and the supplementary formulas for and and multiplicativity of the "numerator".) Problem: Given that 9907 is prime, calculate .Using the Legendre symbol
:Using the Jacobi symbol
: The difference between the two calculations is that when the Legendre symbol is used the "numerator" has to be factored into prime powers before the symbol is flipped. This makes the calculation using the Legendre symbol significantly slower than the one using the Jacobi symbol, as there is no known polynomial-time algorithm for factoring integers.ThePrimality testing
There is another way the Jacobi and Legendre symbols differ. If theSee also
*Notes
References
* * * * * * {{cite journal , title = Efficient Algorithms for Computing the Jacobi Symbol , first1 = Shawna Meyer , last1 = Eikenberry , first2 = Jonathan P. , last2 = Sorenson , journal = Journal of Symbolic Computation , volume = 26 , issue = 4 , pages = 509β523 , date = October 1998 , doi = 10.1006/jsco.1998.0226 , citeseerx = 10.1.1.44.2423 , url = https://core.ac.uk/download/pdf/82664209.pdfExternal links