In number theory, Euler's theorem (also known as the Fermat–Euler theorem or Euler's totient theorem) states that, if n and a are coprime positive integers, then a φ ( n ) } is congruent to 1 modulo n, where φ denotes Euler's totient function; that is a φ ( n ) ≡ 1 ( mod n ) .
Dalam teori bilangan, teorema Euler (dikenal juga sebagai teorema Fermat–Euler atau teorema totien Euler) menyatakan bahwa jika a dan n merupakan bilangan asli yang saling prima, maka a φ ( n ) } akan kongruen dengan 1 dalam modulo n , dengan φ ( n ) menyatakan fungsi phi Euler.
Subsequently, Euler presented other proofs of the theorem, culminating with his paper of 1763, in which he proved a generalization to the case where n is not prime.
Euler kemudian memberikan bukti lain dari teorema tersebut, yang berpuncak pada paper tahun 1763 miliknya, di mana ia membuktikan perumuman untuk kasus n bukan bilangan prima.
The converse of Euler's theorem is also true: if the above congruence is true, then a and n must be coprime.
Konvers dari teorema Euler juga berlaku: jika berlaku kekongruenan di atas, maka a haruslah relatif prima dengan n .
The theorem is further generalized by some of Carmichael's theorems.
Teorema Euler dapat diperumum lebih lanjut dengan teorema Carmichael.
So Euler's theorem yields 7 4 ≡ 1 ( mod 10 ) \equiv 1{\pmod {10}}} , and we get 7 222 ≡ 7 4 × 55 + 2 ≡ ( 7 4 ) 55 × 7 2 ≡ 1 55 × 7 2 ≡ 49 ≡ 9 ( mod 10 )
Berdasarkan teorema Euler, maka didapatkan 7 4 ≡ 1 ( mod 10 ) \equiv 1{\pmod {10}}} .
Euler's theorem underlies the RSA cryptosystem, which is widely used in Internet communications.
Teorema Euler menjadi dasar kriptosistem RSA, yang banyak digunakan dalam komunikasi di internet.
In this cryptosystem, Euler's theorem is used with n being a product of two large prime numbers, and the security of the system is based on the difficulty of factoring such an integer.
Dalam kriptosistem ini, teorema Euler digunakan dengan memilih bilangan n sebagai hasil kali dari dua bilangan prima besar.
Gauss, Carl Friedrich; Clarke, Arthur A. (translated into English) (1986), Disquisitiones Arithemeticae (Second, corrected edition), New York: Springer, ISBN 0-387-96254-9 Gauss, Carl Friedrich; Maser, H. (translated into German) (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition), New York: Chelsea, ISBN 0-8284-0191-8 Hardy, G. H.; Wright, E. M. (1980), An Introduction to the Theory of Numbers (Fifth edition), Oxford: Oxford University Press, ISBN 978-0-19-853171-5 Ireland, Kenneth; Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (Second edition), New York: Springer, ISBN 0-387-97329-X Landau, Edmund (1966), Elementary Number Theory, New York: Chelsea Weisstein, Eric W. "Euler's Totient Theorem".
Gauss, Carl Friedrich; Clarke, Arthur A. (translated into English) (1986), Disquisitiones Arithemeticae (Second, corrected edition), New York: Springer, ISBN 0-387-96254-9 Gauss, Carl Friedrich; Maser, H. (translated into German) (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (edisi kedua), New York: Chelsea, ISBN 0-8284-0191-8 Hardy, G. H.; Wright, E. M. (1980), An Introduction to the Theory of Numbers (Fifth edition)