A natural number greater than 1 that is not prime is called a composite number.
Bilangan asli yang lebih dari 1 dan bukan bilangan prima disebut bilangan komposit.
Faster algorithms include the Miller–Rabin primality test, which is fast but has a small chance of error, and the AKS primality test, which always produces the correct answer in polynomial time but is too slow to be practical.
Algoritma lebih cepatnya adalah uji primalitas Miller–Rabin, algoritma cepat tetapi memiliki kesempatan galat kecil; dan uji primalitas Agrawal–Kayal–Saxena, algoritma yang selalu memberikan solusi yang benar dalam waktu polinomial, tetapi sangat lambat bila dipraktikkan.
Particularly fast methods are available for numbers of special forms, such as Mersenne numbers.
Metode cepat khususnya tersedia dalam bilangan bentuk khusus, seperti bilangan Mersenne.
The numbers greater than 1 that are not prime are called composite numbers.
Bilangan asli yang lebih dari 1 dan bukan bilangan prima disebut bilangan komposit.
42 × 2 and 62 × 3 are both composite.
42 × 2 dan 62 × 3 merupakan bilangan komposit.
Yet another way to express the same thing is that a number ⁠ n ⁠ is prime if it is greater than one and if none of the numbers 2 , 3 , … , n − 1 divides ⁠ n ⁠ evenly.
Ada cara lain untuk menjelaskan hal tersebut, yaitu: n adalah bilangan prima jika n lebih besar dari 1 dan tidak ada bilangan 2 , 3 , … , n − 1 yang membagi n sama rata.
The first 25 prime numbers (all the prime numbers less than 100) are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 (sequence A000040 in the OEIS).
Berikut adalah 25 bilangan prima pertama (semua bilangan prima yang lebih kecil dari 100): 1,2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 (barisan A000040 pada OEIS).
The numbers that end with other digits are all composite: decimal numbers that end in 0, 2, 4, 6, or 8 are even, and decimal numbers that end in 0 or 5 are divisible by 5.
Bilangan yang berakhir dengan digit satuan yang berbeda adalah bilangan komposit: bilangan desimal yang digit satuannya adalah 0, 2, 4, 6, atau 8 adalah bilangan genap, dan bilangan desimal yang berakhir dengan digit satuan 0 dan 5 habis dibagi 5.
The Rhind Mathematical Papyrus, from around 1550 BC, has Egyptian fraction expansions of different forms for prime and composite numbers.
Papirus Matematika Rhind dari sekitar tahun 1550 SM, memiliki perluasan pecahan Mesir dalam bentuk yang berbeda untuk bilangan prima dan bilangan komposit.
Euclid's Elements (c. 300 BC) proves the infinitude of primes and the fundamental theorem of arithmetic, and shows how to construct a perfect number from a Mersenne prime.
Elemen dari Euklides (300 SM) membuktikan bilangan prima tak-hingga dan teorema dasar aritmetika, dan menunjukkan cara membuat bilangan sempurna dari prima Mersenne.
Around 1000 AD, the Islamic mathematician Ibn al-Haytham (Alhazen) found Wilson's theorem, characterizing the prime numbers as the numbers ⁠ n ⁠
Sekitar 1000 M, matematikawan Islam Ibn al-Haytham (Alhazen) menemukan teorema Wilson dengan mencirikan bilangan prima sebagai bilangan n yang membagi rata ( n − 1 ) !
Fibonacci took the innovations from Islamic mathematics to Europe.
Fibonacci membawa inovasi dari matematika Islam kembali ke Eropa.
In 1640 Pierre de Fermat stated (without proof) Fermat's little theorem (later proved by Leibniz and Euler).
Pada 1640, Pierre de Fermat menyatakan teorema kecil Fermat tanpa bukti, yang kemudian dibuktikan oleh Leibniz dan Euler.
Fermat also investigated the primality of the Fermat numbers ⁠ 2 2 n + 1 }+1} ⁠, and Marin Mersenne studied the Mersenne primes, prime numbers of the form 2 p − 1 -1} with ⁠ p ⁠ itself a prime.
Fermat juga menyelidiki primalitas dari bilangan Fermat 2 2 n + 1 }+1} , dan Marin Mersenne mempelajari prima Mersenne, bilangan prima dari bentuk 2 p − 1 -1} dengan p sendiri adalah bilangan prima.
Christian Goldbach formulated Goldbach's conjecture, that every even number is the sum of two primes, in a 1742 letter to Euler.
Dalam surat tahun 1742 untuk Euler, Christian Goldbach merumuskan konjektur Goldbach, bahwa setiap bilangan genap adalah jumlah dari dua bilangan prima.
Euler proved Alhazen's conjecture (now the Euclid–Euler theorem) that all even perfect numbers can be constructed from Mersenne primes.
Euler membuktikan konjektur Alhazen (yang saat ini disebut teorema Euklides–Euler) bahwa semua bilangan sempurna genap dapat dibangun dari bilangan prima Mersenne.
Ideas of Bernhard Riemann in his 1859 paper on the zeta-function sketched an outline for proving the conjecture of Legendre and Gauss.
Gagasan Bernhard Riemann dalam makalahnya tahun 1859 tentang fungsi zeta menggambarkan sebuah garis besar dalam membuktikan konjektur Legendre dan Gauss.
Many mathematicians have worked on primality tests for numbers larger than those where trial division is practicably applicable.
Beberapa matematikawan telah melakukan uji primalitas untuk bilangan lebih besar dari bilangan penerapan uji pembagian.
Methods that are restricted to specific number forms include Pépin's test for Fermat numbers (1877), Proth's theorem (c. 1878), the Lucas–Lehmer primality test (originated 1856), and the generalized Lucas primality test.
Pépin untuk bilangan Fermat (1877), teorema Proth (sekitar 1878), uji primalitas Lucas–Lehmer (berasal dari 1856), dan uji primalitas Lucas rampat.
Since 1951 all the largest known primes have been found using these tests on computers.
Sejak tahun 1951, semua bilangan prima terbesar yang diketahui telah ditemukan menggunakan uji ini pada komputer.
The search for ever larger primes has generated interest outside mathematical circles, through the Great Internet Mersenne Prime Search and other distributed computing projects.
Pencarian bilangan prima besar telah membangkitkan minat pada luar lingkaran matematika, melalui Great Internet Mersenne Prime Search dan proyek komputasi distribusi lainnya.
The idea that prime numbers had few applications outside of pure mathematics was shattered in the 1970s when public-key cryptography and the RSA cryptosystem were invented, using prime numbers as their basis.
Gagasan bahwa bilangan prima memiliki beberapa penerapan diluar matematika murni, sekitar tahun 1970-an ketika kriptografi kunci publik dan RSA sistem kripto ditemukan dengan menggunakan bilangan prima sebagai basisnya.
Most early Greeks did not even consider 1 to be a number, so they could not consider its primality.
Hampir seluruh matematikawan Yunani kuno bahkan tidak menganggap 1 sebagai bilangan, sehingga mereka tidak menganggap primalitas.
The medieval Islamic mathematicians largely followed the Greeks in viewing 1 as not being a number.
Sebagian besar matematikawan Islam pada abad pertengahan mengikuti pandangan matematikawan Yunani bahwa 1 bukanlah sebuah bilangan.
By the Middle Ages and Renaissance, mathematicians began treating 1 as a number, and by the 17th century some of them included it as the first prime number.
Pada masa abad pertengahan dan masa Reinsans, para matematikawan mulai memperlakukan 1 sebagai bilangan, dan ada pula dari mereka memperlakukan 1 sebagai bilangan prima pertama.
In the mid-18th century, Christian Goldbach listed 1 as prime in his correspondence with Leonhard Euler; however, Euler himself did not consider 1 to be prime.
Dalam suratnya untuk Leonhard Euler pada pertengahan abad ke-18, Christian Goldbach menganggap 1 sebagai bilangan prima; tetapi Euler tidak.
For example, the fundamental theorem of arithmetic would need to be rephrased in terms of factorizations into primes greater than 1, because every number would have multiple factorizations with any number of copies of 1.
Sebagai contoh, teorema dasar aritmetika akan perlu ditulis ulang dalam bentuk faktorisasi menjadi bilangan prima lebih besar dari 1, karena setiap bilangan mempunyai banyak kelipatan dengan jumlah salinan dari 1 yang berbeda.
So, although there are many different ways of finding a factorization using an integer factorization algorithm, they all must produce the same result.
Walaupun ada banyak cara mencari faktorisasi melalui algoritma faktorisasi bilangan bulat, hasil yang diperoleh adalah sama.
If the list consists of the primes p 1 , p 2 , … , p n , ,p_{2},\ldots ,p_{n},} this gives the number N1 + p 1 ⋅ p 2 ⋯ p n .
Jikalau terdiri dari bilangan prima p 1 , p 2 , … , p n ,p_{2},\ldots ,p_{n}} , maka N1 + p 1 ⋅ p 2 ⋯ p n \cdot p_{2}\cdots p_{n}} .
3003159 ⋅ 509 , 2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13{\big )}
3003159 ⋅ 509 2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13{\big )}
=30031=59\cdot 509,} is a composite number.
=30031=59\cdot 509} , adalah bilangan komposit.
There is also a set of Diophantine equations in nine variables and one parameter with the following property: the parameter is prime if and only if the resulting system of equations has a solution over the natural numbers.
Adapula himpunan persamaan Diophantus dalam sembilan variabel dan satu parameter dengan sifat berikut: parameter adalah bilangan prima jika dan hanya jika sistem persamaan yang dihasilkan adalah solusi bilangan asli.
Other examples of prime-generating formulas come from Mills' theorem and a theorem of Wright.
Contoh rumus yang menghasilkan bilangan prima lainnya berasal dari teorema Mills dan teorema Wright.
These assert that there are real constants A > 1 and μ such that ⌊ A 3 n ⌋ and ⌊ 2 ⋯ 2 2 μ ⌋ }\right\rfloor {\text{ and }}\left\lfloor 2^{\cdots ^{2^{2^{\mu }}}}\right\rfloor } are prime for any natural number ⁠ n ⁠ in the first formula, and any number of exponents in the second formula.
Rumus ini mengatakan bahwa terdapat suatu konstanta real A > 1 dan μ sehingga ⌊ A 3 n ⌋ }\right\rfloor } dan ⌊ 2 ⋯ 2 2 μ ⌋ }}}\right\rfloor } adalah bilangan prima untuk suatu bilangan asli n dalam rumus yang pertama, dan suatu bilangan eksponen dalam rumus yang kedua.
Often having an elementary formulation, many of these conjectures have withstood proof for decades: all four of Landau's problems from 1912 are still unsolved.
Sering kali memiliki perumusan dasar, banyak konjektur-konjektur tersebut memiliki bukti yang bertahan selama beberapa dekade: empat masalah Landau yang berasal dari tahun 1912 masih belum terpecahkan.
The branch of number theory studying such questions is called additive number theory.
Cabang teori bilangan yang mempelajari masalah tersebut disebut teori bilangan aditif.
+ n consists of n − 1 composite numbers, for any natural number n .
1 } } untuk bilangan asli n yang disebut modulus.
This area of study began with Leonhard Euler and his first major result, the solution to the Basel problem.
Cabang ini dimulai dengan Leonhard Euler yang menemukan solusi dari masalah yang sangat penting, yaitu masalah Basel.
The problem asked for the value of the infinite sum 1 + 1 4 + 1 9 + 1 16 + … , {4}}+{\tfrac {1}{9}}+{\tfrac {1}{16}}+\dots ,} which today can be recognized as the value ζ ( 2 ) of the Riemann zeta function.
Masalah ini menanyakan berapakah nilai dari deret takhingga 1 + 1 4 + 1 9 + 1 16 + … , {4}}+{\tfrac {1}{9}}+{\tfrac {1}{16}}+\dots ,} dan nilai deret saat ini dapat dianggap sebagai nilai ζ ( 2 ) (di mana ζ adalah fungsi zeta Riemann).
This function is closely connected to the prime numbers and to one of the most significant unsolved problems in mathematics, the Riemann hypothesis.
Fungsi ini sangat terkait erat dengan bilangan prima dan fungsi ini merupakan salah satu masalah yang belum terpecahkan yang sangat penting dalam matematika, hipotesis Riemann.
π 2 / 6 /6} ⁠. The reciprocal of this number, ⁠ 6 / π 2 } ⁠, is the limiting probability that two random numbers selected uniformly from a large range are relatively prime (have no factors in common).
Kebalikannya, 6 π 2 {\pi ^{2}}}} , merupakan probabilitas batas yang menyatakan bahwa dua bilangan acak dipilih secara seragam dari kisaran relatif prima yang besar (relatif prima berarti tidak memiliki kesamaan faktor).
For comparison, the sum 1 1 2 + 1 2 2 + 1 3 2 + ⋯ + 1 n 2 {1^{2}}}+{\frac {1}{2^{2}}}+{\frac {1}{3^{2}}}+\cdots +{\frac {1}{n^{2}}}} does not grow to infinity as ⁠ n ⁠ goes to infinity (see the Basel problem).
Bandingkan jumlah 1 1 2 + 1 2 2 + 1 3 2 + ⋯ + 1 n 2 {1^{2}}}+{\frac {1}{2^{2}}}+{\frac {1}{3^{2}}}+\cdots +{\frac {1}{n^{2}}}} , yang tidak naik menuju takhingga ketika n menuju takhingga (lihat masalah Basel).
Methods such as the Meissel–Lehmer algorithm can compute exact values of π ( n ) faster than it would be possible to list each prime up to ⁠ n ⁠.
Metode seperti algoritma Meissel–Lehmer dapat menghitung nilai eksak π ( n ) lebih cepat daripada menulis setiap bilangan prima sampai dengan n .
(n)=\int _{2}^{n}{\frac {dt}{\log t}}.}
∫ 2 n d t log ⁡ t (n)=\int _{2}^{n}{\frac {\mathrm {d} t}{\log t}}} .
For example, 3 , 12 , 21 , 30 , 39 , .
Misalnya, 3 , 12 , 21 , 30 , 39 , .
Modular arithmetic modifies usual arithmetic by only using the numbers ⁠ { 0 , 1 , 2 , … , n − 1 } } ⁠, for a natural number ⁠ n ⁠ called the modulus.
Aritmetika modular memodifikasi aritmetika biasa, hanya saja dengan menggunakan bilangan { 0 , 1 , 2 , … , n −
Equality of integers corresponds to congruence in modular arithmetic: ⁠ x ⁠ and ⁠ y ⁠ are congruent (written x ≡ y mod ⁠ n ⁠)
Kesamaan bilangan bulat sesuai dengan kongruensi dalam aritmetika modular: x dan y adalah kongruen (ditulis x ≡ y mod n ) ketika mereka memiliki sisa yang sama setelah dibagi dengan n .
For instance, with the prime number 7 as modulus, division by 3 is possible: ⁠ 2 / 3 ≡ 3 mod 7 }} ⁠, because clearing denominators by multiplying both sides by 3 gives the valid formula ⁠ 2 ≡ 9 mod 7 }} ⁠.
Misalnya, dengan bilangan prima 7 sebagai modulus, pembagian dengan 3 adalah dimungkinkan: 2 / 3 ≡ 3 mod 7 }} karena kemungkinan menghapus penyebut dengan mengalikan kedua ruas dengan 3 diberikan rumus yang valid 2 ≡ 9 mod 7 }} .
However, with the composite modulus 6, division by 3 is impossible.
Namun, dengan modulus komposit 6 , pembagian dengan 3 adalah hal mustahil.
There is no valid solution to 2 / 3 ≡ x mod 6 }} : clearing denominators by multiplying by 3 causes the left-hand side to become 2 while the right-hand side becomes either 0 or 3.
Tidak ada solusi yang valid untuk 2 / 3 ≡ x mod 6 }} : menghapus penyebut dengan mengalikan dengan 3 menyebabkan ruas kiri menjadi 2 sedangkan ruas kanan menjadi 0 atau 3 .
In the terminology of abstract algebra, the ability to perform division means that modular arithmetic modulo a prime number forms a field or, more specifically, a finite field, while other moduli only give a ring but not a field.
Dalam terminologi aljabar abstrak, kemampuan untuk melakukan pembagian berarti bahwa modulo aritmetika modular bilangan prima membentuk medan atau medan berhingga, sedangkan modulus lainnya hanya memberikan gelanggang tetapi bukan sebuah medan.
Several theorems about primes can be formulated using modular arithmetic.
Beberapa teorema tentang bilangan prima dirumuskan menggunakan aritmetika modular.
For instance, Fermat's little theorem states that if a ≢ 0 (mod ⁠ p ⁠), then a p − 1 ≡ 1 \equiv 1} (mod ⁠ p ⁠).
Misalnya, teorema kecil Fermat menyatakan bahwa jika a ≢ 0 (mod p ), maka a p − 1 ≡ 1 \equiv 1} (mod p ).
⋅ 1 ≡ − 1 ( mod p ) , ^{p-1}a^{p-1}\equiv (p-1)\cdot 1\equiv -1{\pmod {p}},} valid whenever ⁠ p ⁠ is prime.
Menjumlahkan dari semua pilihan a diberikan persamaan ∑ a1 p − 1 a p − 1 ≡ ( p − 1 ) ⋅ 1 ≡ − 1 ( mod p ) , ^{p-1}a^{p-1}\equiv (p-1)\cdot 1\equiv -1{\pmod {p}},} valid jika p adalah bilangan prima.
Giuga's conjecture says that this equation is also a sufficient condition for ⁠ p ⁠ to be prime.
Konjektur Giuga menyebutkan bahwa persamaan ini juga merupakan syarat yang cukup untuk p menjadi prima.
Wilson's theorem says that an integer p > 1 is prime if and only if the factorial ( p − 1 ) !
Teorema Wilson menyebutkan bahwa sebuah bilangan bulat p > 1 adalah bilangan prima jika dan hanya jika faktorial ( p − 1 ) !
⁠, and so ( n − 1 ) !
, dan jadi ( n − 1 ) !
≡ − 1 ( mod n ) }} is impossible.
≡ − 1 ( mod n ) }} adalah hal mustahil.
Just as the distance between two real numbers can be measured by the absolute value of their distance, the distance between two rational numbers can be measured by their ⁠ p ⁠-adic distance, the ⁠ p ⁠-adic absolute value of their difference.
Sama seperti jarak antara dua bilangan real yang dapat diukur dengan nilai absolut jaraknya, jarak antara dua bilangan rasional dapat diukur dengan jarak p -adik-nya, nilai absolut p -adik dari selisihnya.
For this definition of distance, two numbers are close together (they have a small distance) when their difference is divisible by a high power of ⁠ p ⁠.
Untuk definisi jarak ini, dua bilangan dikatakan berdekatan (memiliki jarak yang kecil) ketika selisihnya habis dibagi dengan pangkat p yang tinggi.
In the same way that the real numbers can be formed from the rational numbers and their distances, by adding extra limiting values to form a complete field, the rational numbers with the ⁠ p ⁠-adic distance can be extended to a different complete field, the ⁠ p ⁠-adic numbers.
Dengan cara yang sama bahwa bilangan real dapat dibentuk dari bilangan rasional dan jaraknya, dengan menambahkan nilai pembatas ekstra untuk membentuk medan lengkap, bilangan rasional dengan jarak p -adik diperluas ke medan lengkap yang berbeda.
The extension from the rational numbers to the real numbers, for instance, is a place in which the distance between numbers is the usual absolute value of their difference.
Perluasan dari bilangan rasional ke bilangan real, misalnya adalah tempat di mana jarak antara bilangan adalah nilai absolut biasa dari perbedaannya.
The corresponding mapping to an additive group would be the logarithm of the absolute value, although this does not meet all the requirements of a valuation.
Pemetaan yang sesuai ke grup aditif akan menjadi logaritma dari nilai absolut, meskipun ini tidak memenuhi semua persyaratan penilaian.
According to Ostrowski's theorem, up to a natural notion of equivalence, the real numbers and ⁠ p ⁠-adic numbers, with their orders and absolute values, are the only valuations, absolute values, and places on the rational numbers.
Menurut teorema Ostrowski, gagasan ekuivalen alami berhingga, bilangan real dan bilangan p -adik dengan urutan dan nilai absolutnya adalah satu-satunya penilaian, nilai absolut, dan tempat pada bilangan rasional.
The local–global principle allows certain problems over the rational numbers to be solved by piecing together solutions from each of their places, again underlining the importance of primes to number theory.
Prinsip lokal-global memungkinkan masalah tertentu atas bilangan rasional untuk diselesaikan dengan menyatukan solusi dari masing-masing tempat, sekali lagi menggarisbawahi pentingnya bilangan prima untuk teori bilangan.
The fundamental theorem of arithmetic continues to hold (by definition) in unique factorization domains.
Teorema dasar aritmetika tetap berlaku (menurut definisi) dalam domain faktorisasi tunggal.
For instance, in the ring of numbers a + b − 5 }} (for integers ⁠ a ⁠ and ⁠ b ⁠)
Misalnya, dalam bilangan gelanggang a + b − 5 }} (untuk bilangan bulat a dan b )
the number 21 has two factorizations ⁠ 213 ⋅ 7( 1 + 2 − 5 ) ( 1 − 2 − 5 ) })(1-2{\sqrt {-5}})} ⁠, where none of the four factors can be reduced any further, so it does not have a unique factorization.
angka 21 memiliki dua faktorisasi 213 ⋅ 7( 1 + 2 − 5 ) ( 1 − 2 − 5 ) })(1-2{\sqrt {-5}})} , tidak satu pun dari keempat faktor tersebut bisa direduksi lebih jauh, sehingga tidak memiliki faktorisasi unik.
In order to extend unique factorization to a larger class of rings, the notion of a number can be replaced with that of an ideal, a subset of the elements of a ring that contains all sums of pairs of its elements, and all products of its elements with ring elements.
Untuk memperluas faktorisasi unik pada kelas gelanggang terbesar, gagasan tentang bilangan bisa diganti dengan ideal, sebuah himpunan bagian dari elemen gelanggang yang memuat semua jumlah pasangan elemennya, dan semua hasil kali elemennya dengan elemen gelanggang.
The fundamental theorem of arithmetic generalizes to the Lasker–Noether theorem, which expresses every ideal in a Noetherian commutative ring as an intersection of primary ideals, which are the appropriate generalizations of prime powers.
Teorema dasar aritmetika digeneralisasikan ke teorema Lasker–Noether disebutkan setiap ideal dalam gelanggang komutatif Noetherian sebagai perpotongan ideal prima yang merupakan generalisasi yang tepat dari prima kuasa.
Arithmetic geometry also benefits from this notion, and many concepts exist in both geometry and number theory.
Geometri aritmetika juga mendapat manfaat dari gagasan ini, dan banyak konsep yang ada, baik dalam geometri maupun teori bilangan.
These concepts can even assist with in number-theoretic questions solely concerned with integers.
Konsep-konsep ini bahkan dapat membantu dalam pertanyaan teori bilangan yang hanya berkaitan dengan bilangan bulat.
Early attempts to prove Fermat's Last Theorem led to Kummer's introduction of regular primes, integer prime numbers connected with the failure of unique factorization in the cyclotomic integers.
Upaya awal untuk membuktikan Teorema Terakhir Fermat menyebabkan pengenalan Kummer dari prima regular, bilangan prima bilangan bulat terhubung dengan kegagalan faktorisasi unik pada bilangan bulat siklotomi.
Prime Numbers on In Our Time at the BBC.
Prime Numbers di In Our Time di BBC.
Prime factors calculator can factorize any positive integer up to 20 digits.
Kalkulator faktor prima bisa memfaktorkan bilangan bulat positif apa pun hingga 20 digit.