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

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

⎛ ⎜ ⎜ ⎝ |
a
n
| ⎞ ⎟ ⎟ ⎠ | = | ⎧ ⎪ ⎨ ⎪ ⎩ |
0 | if a=0 modn
1 | if a ≠ 0 modn και if a=b2 modn
−1 | if a ≠ 0 modn και if a ≠ b2 modn

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

- Αν 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`