Congruences

Kroz ovaj diplomski rad bavit ćemo se kongruencijama. Teorija kongruencija pripada teoriji brojeva, a za njezin razvoj posebno su značajni matematičari Johann Carl Friedrich Gauss, Leonhard Euler, Pierre de Fermat te Joseph-Louis Lagrange. Prvo ćemo se upoznati s pojmom kongruencije te proći kroz osnovna svojstva. Nadalje, definirat ćemo klasu ostataka modulo m, navesti odgovarajuća svojstva i definirati potpuni sustav ostataka modulo m. Proučavat ćemo polinomijalne kongruencije, odnosno navest ćemo te dokazati uvjete postojanosti rješenja takvih kongruencija te broj rješenja istih. U radu ćemo definirati Eulerovu funkciju te navesti njezina svojstva. Pomoću te funkcije uvest ćemo pojam reduciranog sustava ostataka te iskazati i dokazati Euler-Fermatov teorem. Nakon toga slijedi iskaz i dokaz Lagrangeovog teorema koji govori o poveznici broja rješenja polinomijalne kongruencije te njezina stupnja. Nastavno na to, prikazat ćemo neke primjene Lagrangeovog teorema. Također ćemo promatrati sustave linearnih kongruencija, odnosno pokazat ćemo kako sustav dviju ili više linearnih kongruencija svaka od kojih ima jedinstveno rješenje, također ima rješenje u slučaju kada su moduli kongruencija u parovima relativno prosti. O tome nam govori Kineski teorem o ostatcima i njegova generalizacija. Navest ćemo i neke od primjena Kineskog teorema, od kojih jedna prikazuje kako se može reducirati problem rješavanja polinomijalnih kongruencija. Iskazat ćemo i dokazati teorem o prebrojavanju skupova koji se naziva Princip unakrsne klasifikacije te kroz primjer prikazati izvod za produkt Eulerove funkcije pomoću tog principa. Na kraju ćemo pokazati kako se pomoću Principa unakrsne klasifikacije može napraviti dekompozicija reduciranih sustava ostataka modulo m. Sve navedeno potkrijepit ćemo primjerima.Through this thesis we will deal with congruences. The theory of congruences is part of theory of numbers, and the mathematicians Johann Carl Friedrich Gauss, Leonhard Euler, Pierre de Fermat and Joseph-Louis Lagrange are especially important for its development. First, we will get acquainted with the concept of congruence and go through the basic properties. Furthermore, we will define the residue class modulo m, list the corresponding properties and define a complete residue system modulo m. We will study polynomial congruences, that is, we will state and prove conditions of existence of solutions of such congruences and the number of solutions. In this paper, we will define the Euler totient function and state its properties. Using this function, we will introduce the notion of a reduced residue system and state and prove the Euler-Fermat theorem. This is followed by the statement and proof of Lagrange’s theorem, which speaks of relationship of the number of solutions of polynomial congruence and of her degree. Next, we will present some applications of Lagrange’s theorem. We will also look at simultaneous linear congruences, i.e we will show how a system of two or more linear congruences each of which has a unique solution, also has a solution in the case where modules of congruences are relatively prime in pairs. This is dealt with by the Chinese remainder theorem and the generalization of that theorem. We will also list some of the applications of the Chinese theorem, one of which shows how the problem of solving polynomial congruences can be reduced. We will state and prove a set counting theorem called the Principle of cross-classification and through an example show the derivative for the product of the Euler totient function using this principle. Finally, we will show how decomposition of reduced residue systems modulo m can be done using the Principle of cross-classification. We will support all of the above with examples