Μαθηματικό Υπόβαθρο

Abstract

Διαιρετότητα, πρώτοι αριθμοί, το Θεμελιώδες Θεώρημα της Αριθμητικής. Αριθμητική modulo, ο δακτύλιος Ζn. Ιδιότητες πράξεων στο Zn. Κινέζικο Θεώρημα Υπολοίπων, συνάρτηση φ του Euler, Θεωρήματα Fermat και Euler. Ομάδες, σύμπλοκα, θεώρημα Lagrange. Γεννήτορες, τάξη ομάδας, Θεμελιώδες Θεώρημα κυκλικών ομάδων. Οι πολλαπλασιαστικές ομάδες Zp* και U(Zn). Κυκλικότητα της Zp*. Τετραγωνικά υπόλοιπα, υπολογισμός ριζών modulo n, σύμβολα Legendre και Jacobi. Ο νόμος τετραγωνικής αντιστροφής. Αριθμητική πολυωνύμων πάνω σε πεπερασμένα σώματα. Στοιχεία διακριτής πιθανότητας. Το παράδοξο των γενεθλίων.

Divisibility, prime numbers, the Fundamental Theorem of Arithmetic. Arithmetic modulo, the ring Zn. Properties of operations in Zn. Chinese Remainder Theorem, Euler's φ function, Fermat's and Euler's Theorems. Groups, subgroups, Lagrange's Theorem. Generators, order of a group, Fundamental Theorem of Cyclic Groups. The multiplicative groups Zp* and U(Zn). Cyclicity of Zp*. Quadratic residues, computation of roots modulo n, Legendre and Jacobi symbols. The law of quadratic reciprocity. Polynomial arithmetic over finite fields. Elements of discrete probability. The birthday paradox.