This is intuitively clear once one observes that more and more prime numbers are used in the sieving process as the numbers get bigger. Identify all the composite numbers from to that are sieved by 11 and 13, but were not sieved by 2, 3, 5 or 7.
Testing whether a reasonably large number is prime is a massive computing problem. One important insight, however, greatly reduces the amount of computation required. Students will have noticed from the Sieve of Eratosthenes that when finding all primes up to , it was only necessary to sieve by the primes 2, 3, 5 and 7. The general principle is:. Any number n that is to be tested in school mathematics should thus yield to the following plan of attack:.
It is usual to write the prime factorisation in index form with the primes in increasing order,. List the primes that are needed when the Sieve of Eratosthenes is applied to find all the primes up to How many final zeroes are there in the number 30!
Awareness of prime divisors can greatly simplify mental arithmetic problems. Combining factors of 2 and 5 together is always useful:. In other situations, dealing separately with different prime divisors can be helpful:.
Once the prime factorisation of a number has been obtained, all its factors can quickly be written down. For example,. Prime factorisation and square roots. Once the index laws have been established for whole-number indices, whole-number square roots can be found from the prime factorisation of a number by halving the indices, provided that all the indices are even.
List in index form all the whole number square roots, cube roots and higher roots of 2 The method is easier once the zero index has been introduced.
If the zero index has not been introduced when students study this material, then the situation where a prime is missing from one of the prime factorisations will need to be explained separately:.
The last three parts of the next exercise are true for any two whole numbers. The calculations below can quickly be adapted for any pair of numbers, once their prime factorisations have been found. The working on the right below shows a concise way to lay out the working for find the HCF and LCM of two numbers, using the same numbers and as in the example above:.
Repeat the method with the numbers and , including the prime factorisations. Irreducible polynomials play a role in algebra analogous to the role of prime numbers in arithmetic. Moreover, factoring of polynomials can be used to factor numbers. For example, 91 can be factored using the identity above,. With this definition, every integer can be factored into prime integers, but the factorisation is only unique if primes in the factorisation are allowed to be replaced by their opposites.
The following factorisation of the prime 5 involving the imaginary number i shows that primes have to be defined quite differently when working with complex numbers:. Although primes were probably known to the Egyptians, the first known study of them occurs in the Elements of the Greek mathematician Euclid about BC.
Euclid proved that every number can be factored uniquely into primes, and also proved that there are infinitely many prime numbers. In , Goldbach famously conjectured that every even number greater than 2 is the sum of two prime numbers. Prime pairs stand out in the list of primes up to Mathematics is full of unsolved problems. Wikipedia is a good place to find links to the present state of these and other outstanding problems.
Both the Goldback Conjecture and the twin prime conjecture are thought to be true. The largest known prime. There is no known algorithm for generating arbitrarily large prime numbers. Prime numbers of this type are called Mersenne primes , and the index of 2 in such a prime must be a prime number. Applications of primes in security codes. One of the most important problems in everyday life is the secure transmission of information.
Prime numbers are used in computing as a means of encoding information so that it can be kept secure.
Although in theory, every whole number is a product of primes, in practice it is very hard to find the actual factorisation of a very large number, even using high speed modern computers. Computer scientists exploit this fact to build codes that are very hard to break, using very large prime numbers. The primes 3, 7, 11 form an arithmetic sequence of three primes.
An arithmetic sequence is a sequence that increases at each step by a common difference , which in this case is 4. The primes 5, 11, 17, 23, 29 form an arithmetic sequence of five primes — in this case the common difference is 6. In , Terence Tao from Australia and Ben Green from the UK proved that there are arithmetic sequences of primes of any given length.
For this and other work, Tao in became the first Australian to be awarded a Fields Medal, which is considered to be equivalent to a Nobel Prize in Mathematics..
Find an arithmetic sequence of six or more primes. The record at the time of writing is a sequence of 25 primes found in , but see Wikipedia for more details. Sequences of successive composite numbers. In contrast to these difficult questions about primes, the following exercise easily shows that there are sequences of arbitrary length consisting only of successive composite numbers. But 6 is not a prime number, so we need to go further. Example: What is the prime factorization of ?
Can we divide exactly by 2? The next prime, 5, does not work. Example: What is the prime factorization of 17? Hang on Say : There is a theorem in mathematics that says when we factor a number into a product of prime numbers, it can only be done one way, not counting the order of the factors.
Say : Now let's try one on your own. Find the prime factorization of 60 by creating a factor tree for Have all students independently factor As they complete their factorizations, observe what students do and take note of different approaches and visual representations.
Ask for a student volunteer to factor 60 for the entire class to see. Ask : Who factored 60 differently? Have students who factored 60 differently either by starting with different factors or by visually representing the factor tree differently show their work to the class. Ask students to describe similarities and differences in the factorizations.
If no one used different factors, show the class a factorization that starts with a different set of factors for 60 and have students identify similarities and differences between your factor tree and other students'. The students should say no, because 9 is not a prime number. If they don't, remind them that the prime factorization of a number means all the factors must be prime and 9 is not a prime number.
Developing the Concept: Product of Prime Numbers Now that students can find the prime factorization for numbers which are familiar products, it is time for them to use their rules for divisibility and other notions to find the prime factorization of unfamiliar numbers. Say : Yesterday, we wrote some numbers in their prime factorization form. Ask : Who can write 91 as a product of prime numbers?
Many students might say it can't be done, because they will recognize that 2, 3, 4, 5, 9 and 10 don't divide it. They may not try to see if 7 divides it, which it does. If they don't recognize that 7 divides 91, demonstrate it for them. Next, write the number on the board. Ask : Who can tell me two numbers whose product is ? Students are likely to say 10 and If not, ask them to use their rules for divisibility to see if they can find two numbers. Create a factor tree for like the one below.
Ask : How many factors of two are there in the prime factorization of ? If you start with 2 and , you end up with the same prime factorization in the end, but you end up with a "one-sided tree" that some students may find more difficult to work with. Have students identify ways that they prefer to factor and guide them to explain their reasoning. Prime numbers like 7 and 11 will not divide the number, because they do not appear in the prime factorization of the number.
Write the number on the board. Ask : What two numbers might we start with to find the prime factorization of ? What other numbers could we use? Encourage students to find a variety of pairs, such as 10 and 18 or 9 and If no one mentions either pair, suggest them both as possibilities. Have half the students use 10 and 18 and the other half use 9 and Have two students create the two factors for the class to see. Repeat the previous exercise with a new number.
0コメント