Ευκλείδεια διαίρεση

Στα μαθηματικά, **Ευκλείδεια διαίρεση** (ή **αλγοριθμική διαίρεση**) είναι ένας οποιοσδήποτε αλγόριθμο για την διαίρεση ενός ακεραίου αριθμού με έναν άλλον. Πιο συγκεκριμένα, ένας αλγόριθμος που έχει ως εισόδους δύο ακεραίους τον \Delta (τον διαιρετέο) και τον διαιρέτη \delta \neq 0, και που επιστρέφει δύο άλλους ακεραίους, το πηλίκο \Pi και το υπόλοιπο \upsilon, ώστε
:\Delta = \delta \cdot \Pi + \upsilon και 0 \leq \upsilon .
Για παράδειγμα, η Ευκλείδεια διαίρεση του \Delta = 37 με το \delta = 8 δίνει ως αποτέλεσμα το πηλίκο \Pi = 4 και υπόλοιπο \upsilon = 5, καθώς 37 = 8 \cdot 4 + 5.

Το **θεώρημα της διαίρεσης** λέει ότι για δοσμένα \Delta και \delta, το πηλίκο \Pi και το υπόλοιπο \upsilon υπάρχουν και είναι μοναδικά. Ο πιο κοινός αλγόριθμος για την διαίρεση είναι η κάθετη διαίρεση, αλλά υπάρχουν και άλλοι. 

Οι αλγόριθμοι είναι θεμελιώδεις για τον κλάδο της υπολογιστικής θεωρίας αριθμών, που βρίσκει πολλές εφαρμογές στην κρυπτογραφία, την ανάλυση δεδομένων και γενικότερα στην πληροφορική.

## Παραδείγματα
* Η Ευκλείδεια διαίρεση του \Delta = 26 με το \delta = 7 δίνει ως αποτέλεσμα το πηλίκο \Pi = 3 και υπόλοιπο \upsilon = 5, καθώς 26 = 7 \cdot 3 + 5.
* Η Ευκλείδεια διαίρεση του \Delta = 137 με το \delta = 15 δίνει ως αποτέλεσμα το πηλίκο \Pi = 9 και υπόλοιπο \upsilon = 5, καθώς 137 = 15 \cdot 9 + 2.

Και με αρνητικούς αριθμούς
* Η Ευκλείδεια διαίρεση του \Delta = -26 με το \delta = -7 δίνει ως αποτέλεσμα το πηλίκο \Pi = 4 και υπόλοιπο \upsilon = 2, καθώς -26 = (-7) \cdot 4 + 2.
* Η Ευκλείδεια διαίρεση του \Delta = -26 με το \delta = 7 δίνει ως αποτέλεσμα το πηλίκο \Pi = -4 και υπόλοιπο \upsilon = 2, καθώς -26 = 7 \cdot (-4) + 2.
* Η Ευκλείδεια διαίρεση του \Delta = 26 με το \delta = -7 δίνει ως αποτέλεσμα το πηλίκο \Pi = -3 και υπόλοιπο \upsilon = 2, καθώς 26 = (-7) \cdot (-3) + 5.

## Θεώρημα διαίρεσης

### Απόδειξη
Η απόδειξη χωρίζεται σε δύο τμήματα, την ύπαρξη του πηλίκου και του υπολοίπου, και την μοναδικότητά τους. 

## Παραδείγματα αλγορίθμων

Παρακάτω δίνονται δύο βασικά παραδείγματα αλγορίθμων που υλοποιούν την Ευκλείδεια διαίρεση. Ο δεύτερος είναι πιο αποδοτικός από τον πρώτο, με την έννοια ότι γενικά χρειάζεται λιγότερες πράξεις για να δώσει το αποτέλεσμα. Για χάριν ευκολίας, οι παρακάτω αλγόριθμοι παρουσιάζονται για τους φυσικούς αριθμούς.

### Επαναλαμβανόμενη αφαίρεση

Ο πιο απλός αλγόριθμος είναι να ξεκινήσουμε από το \Delta και κάθε φορά να αφαιρούμε \delta από αυτόν μέχρι να φτάσουμε σε μία τιμή που είναι μικρότερη από \delta. Αυτός ο αλγόριθμος χρειάζεται \Theta(\Pi) πράξεις.


```c++
pair<int, int> euclidean_division(int D, int d) {
   int P = 0;
   int u = D;
   while (u > d) {
      P = P + 1;
      u = u - d;
   }
   return {P, u};
}
```


### Κάθετη διαίρεση

Η κάθετη διαίρεση που μαθαίνουμε στο σχολείο είναι πολύ πιο γρήγορη καθώς χρειάζεται \Theta(\log_{10} \Pi) πράξεις. Ο παρακάτω κώδικας δίνει μία υλοποίηση.


```c++
pair<int, int> euclidean_division(int D, int d) {
   int P = 0;
   int pow10 = 1;
   while (d * pow10 <= D) pow10 *= 10; 
   int u = D;
   while (u >= d) {
      int digit = 0;
      while ((digit + 1) * pow10 * d <= u) {
         digit = digit + 1;
      }
      u -= digit * pow10 * d;
      P += digit * pow10;
      pow10 /= 10;
   }
   return {P, u};
}
```


## Δείτε επίσης
* Διαίρεση
* Κάθετη διαίρεση

## Σημειώσεις


## Παραπομπές


Κατηγορία:Θεωρία αριθμών