Ακέραιοι Αριθμοί

Abstract

In this chapter we study the basic properties of the divisibility of integer numbers and the time of execution of theirs elementary arithmetical operations. More precisely, we begin from the Euclidean division, we prove the unicity of g-adic expansion of an integer<br/>(where g is a fixe positive number) and we introduce the notion of the length of an integer. Next, we deal with the notion<br/>of binary digital operation, we compute the number of binary digital operation needed for the execution of elementary arithmetical operations and we introduce the reader to the algorithms and theirs running time. We give examples of elementary algorithms and the Karatsuba algorithm for fast integer multiplication. We introduce the notions of greatest common divisor and the least common multiple of two integers and we give theirs basic properties. Furthermore, we present the extended Euclidean algorithm and we compute its running time. Finally, we study the solvability of the linear Diophantine equation.

Στο κεφάλαιο αυτό μελετάμε τις βασικές ιδιότητες της διαιρετότητες των ακεραίων αριθμών και τον χρόνο εκτέλεσης των στοιχειωδών πράξεων της αριθμητικής τους. Πιο συγκεκριμένα αρχίζοντας με την Ευκλείδεια διαίρεση αποδεικνύουμε την μοναδικότητα της γραφής ενός τυχόντος ακεραίου στην κλίμακα ενός δοθέντος θετικού ακεραίου και εισάγουμε την έννοια του μήκους ενός ακεραίου. Κατόπιν, ασχολούμαστε με την έννοια της δυαδικής ψηφιακής πράξης, υπολογίζουμε το πλήθος των δυαδικών ψηφιακών πράξεων που απαιτεί η εκτέλεση των στοιχειωδών αριθμητικών πράξεων και και εισάγουμε τον αναγνώστη<br/>στους αλγόριθμους και τον χρόνο εκτέλεσης τους. Επιπλέον, μελετάμε παραδείγματα στοιχειωδών αλγορίθμων καθώς και τον αλγόριθμο ταχύτερου πολλαπλασιασμού δύο ακεραίων του A. Karatsuba. Εισάγουμε τις έννοιες του μέγιστου κοινού διαιρέτη, ελαχίστου κοινού πολλαπλασίου δύο ακεραίων και δίνουμε βασικές ιδιότητές τους. Κατόπιν, περιγράφουμε τον εκτεταμένο Ευκλείδειο αλγόριθμο και υπολογίζουμε τον χρόνο εκτέλεσής του. Τέλος, μελετάμε την επίλυση των γραμμικών Διοφαντικών εξισώσεων.