Úvod

Publikácia sa venuje zovšeobecneniu Eulerovej a Fermatovej vety s použitím funkcie GCD čiže najväčší spoločný deliteľ. Naviac, poskytujem riešenie modulárnej aritmetiky, keď máme zadané a^b mod n, pričom b a n môžu nadobúdať obrovské hodnoty.

Na riešenie problému je využitá redukcia exponentu podľa Eulerovej funkcie. Ako návod poskytujem kód v jazyku C#, ktorý je upravený tak, aby zvládal obrovské čísla a poskytuje všeobecnejší pohľad na Eulera a Fermata.

Redukcia exponentu v modulárnej aritmetike

V modulárnej aritmetike často potrebujeme vypočítať a^b mod n, kde a, b a n sú celé čísla. Ak sú tieto hodnoty veľké, priamy výpočet je nepraktický. Tu prichádzajú na rad Fermatova a Eulerova veta, ktoré nám umožňujú redukovať veľkosť exponentu.

Redukcia exponentu pri modulárnej aritmetike

Eulerova veta

Ak a a n sú kladné celé čísla a gcd(a, n) = 1 (sú nesúdeliteľné), potom:

a^φ(n) ≡ 1 (mod n)

kde φ(n) je Eulerova funkcia, ktorá počíta počet čísel od 1 do n, ktoré sú nesúdeliteľné s n.

Fermatova malá veta

Špeciálnym prípadom Eulerovej vety je Fermatova malá veta. Ak p je prvočíslo a a nie je deliteľné číslom p, potom:

a^p-1 ≡ 1 (mod p)

Zovšeobecnenie pre prípad gcd(a, n) > 1

Klasické verzie týchto viet vyžadujú, aby a a n boli nesúdeliteľné. V našom zovšeobecnení sa tohto obmedzenia zbavíme.

Vizualizácia algoritmu redukcie

Algoritmus redukcie exponentu

Nasledujúci algoritmus rieši problém a^b mod n aj pre prípady, keď gcd(a, n) > 1:

1. Nájdi d = gcd(a, n)
2. Ak d = 1, použi štandardnú Eulerovu vetu
3. Ak d > 1:
   • Ak b < k, kde k je najmenšie celé číslo také, že d^k delí n, vypočítaj priamo
   • Inak, použi redukciu exponentu na základe novej vety

Hlavná veta

Pre kladné celé čísla a, b, n, kde d = gcd(a, n) a d > 1, platí:

Ak b ≥ k, kde k je najmenšie celé číslo také, že d^k delí n, potom a^b ≡ 0 (mod n)

Ak b < k, použijeme vzorec: a^b ≡ (a/d)^b × d^b (mod n)

Implementácia algoritmu

Zdrojový kód pre implementáciu algoritmu je dostupný v mojom GitHub repozitári. Algoritmus je účinný aj pre obrovské hodnoty a, b a n.

Tento zovšeobecnený prístup má praktické aplikácie v kryptografii, teórii čísel a ďalších oblastiach matematiky, kde sa pracuje s modulárnou aritmetikou veľkých čísel.

Záver

Zovšeobecnenie Eulerovej a Fermatovej vety predstavuje významný krok v oblasti teórie čísel a poskytuje efektívny nástroj pre prácu s modulárnou aritmetikou. Algoritmus redukcie exponentu umožňuje rýchly výpočet aj pre extrémne veľké hodnoty vstupných parametrov.

Introduction

This publication deals with the generalization of Euler's and Fermat's theorem using the GCD function, i.e., the greatest common divisor. Additionally, I provide a solution for modular arithmetic when we have a^b mod n, where b and n can take on huge values.

The solution uses exponent reduction according to Euler's function. As a guide, I provide code in C# that is adapted to handle huge numbers and provides a more general view of Euler and Fermat.

Exponent Reduction in Modular Arithmetic

In modular arithmetic, we often need to calculate a^b mod n, where a, b and n are integers. If these values are large, direct calculation is impractical. Here come Fermat's and Euler's theorems, which allow us to reduce the size of the exponent.

Exponent reduction in modular arithmetic

Euler's Theorem

If a and n are positive integers and gcd(a, n) = 1 (they are coprime), then:

a^φ(n) ≡ 1 (mod n)

where φ(n) is Euler's totient function, which counts the number of integers from 1 to n that are coprime to n.

Fermat's Little Theorem

A special case of Euler's theorem is Fermat's little theorem. If p is a prime and a is not divisible by p, then:

a^p-1 ≡ 1 (mod p)

Generalization for the case gcd(a, n) > 1

Classical versions of these theorems require that a and n be coprime. In our generalization, we get rid of this restriction.

Visualization of reduction algorithm

Exponent Reduction Algorithm

The following algorithm solves the problem a^b mod n even for cases when gcd(a, n) > 1:

1. Find d = gcd(a, n)
2. If d = 1, use standard Euler's theorem
3. If d > 1:
   • If b < k, where k is the smallest integer such that d^k divides n, calculate directly
   • Otherwise, use exponent reduction based on the new theorem

Main Theorem

For positive integers a, b, n, where d = gcd(a, n) and d > 1, it holds:

If b ≥ k, where k is the smallest integer such that d^k divides n, then a^b ≡ 0 (mod n)

If b < k, we use the formula: a^b ≡ (a/d)^b × d^b (mod n)

Algorithm Implementation

The source code for the algorithm implementation is available in my GitHub repository. The algorithm is efficient even for huge values of a, b and n.

This generalized approach has practical applications in cryptography, number theory, and other areas of mathematics where modular arithmetic with large numbers is used.

Conclusion

The generalization of Euler's and Fermat's theorem represents a significant step in the field of number theory and provides an efficient tool for working with modular arithmetic. The exponent reduction algorithm enables fast computation even for extremely large values of input parameters.