### 1.6.26 Το σύμβολο του Legendre: legendre_symbol

Αν n είναι πρώτος, ορίζουμε το σύμβολο του Legendre του a γραμμένο (a/n) όπου :

⎛
⎜
⎜
⎝

a
n

⎞
⎟
⎟
⎠

=

⎧
⎪
⎨
⎪
⎩

0 | if a=0 modn
1 | ifa≠ 0 modnκαι ifa=b2modn
−1 | ifa≠ 0 modnκαι ifa≠b2modn

Ορισμένες ιδιότητες

- Αν n είναι πρώτος :

  a

  n−1
  2

  =

  ⎛
  ⎜
  ⎜
  ⎝

  a
  n

  ⎞
  ⎟
  ⎟
  ⎠

  modn

- ⎛
  ⎜
  ⎜
  ⎝

  p
  q

  ⎞
  ⎟
  ⎟
  ⎠

  .

  ⎛
  ⎜
  ⎜
  ⎝

  q
  p

  ⎞
  ⎟
  ⎟
  ⎠

  =

  (−1)

  p−1
  2

  .(−1)

  q−1
  2

  αν p και q είναι περιττοί και θετικοί

  ⎛
  ⎜
  ⎜
  ⎝

  2
  p

  ⎞
  ⎟
  ⎟
  ⎠

  =

  (−1)

  p2−1
  8

  ⎛
  ⎜
  ⎜
  ⎝

  −1
  p

  ⎞
  ⎟
  ⎟
  ⎠

  =

  (−1)

  p−1
  2

legendre_symbol παίρνει δύο ορίσματα a και n και επιστρέφει το σύμβολο του Legendre (a/n).
Είσοδος :

legendre_symbol(26,17)

Έξοδος :

1

Είσοδος :

legendre_symbol(27,17)

Έξοδος :

-1

Είσοδος :

legendre_symbol(34,17)

Έξοδος :

0