Last time we looked at basic methods for finding the prime factorization of a number. Here we will look at some special techniques for large numbers, demonstrating them for not-too-large numbers. This takes us a step beyond previous tests that told us whether a number was composite, without actually factoring them.
I’ll close this series on prime numbers by looking at how to find the prime factorization of a number, starting with the most basic ideas applicable to relatively small numbers, and then (next week) looking at some advanced methods for larger numbers.
Last time we saw how to test small or medium sized numbers to see if they are prime, including details on the elementary Trial Division method, and introduced the most popular test for larger numbers, the Fermat test. Here we’ll review Fermat, and then go beyond. This is not for the faint-hearted! (I myself am …
Last time we looked at how to efficiently make a list of prime numbers. But if you want to check a single large number to see if it is a prime, you don’t want to have to make a list of all primes up to that number. That’s today’s subject, where we’ll start with Trial …
We’ve looked at what prime numbers are, and how the concept extends (or doesn’t) to 0, 1, and negative integers. The next question many students have is, how can I make a list of prime numbers (or write a computer program to do so)? We’ll learn about the Sieve of Eratosthenes, and list all the …
We’ve looked at the basic idea of primes, then at where 0 and 1 fit in. But what about negative integers? Can they be prime? If so, how does that affect the definition? And can you factorize a negative number if you don’t have negative primes?
Last week we looked at the definitions of prime and composite numbers, and saw that 1 is neither. The same is true of 0. What, then, are they? That raises some deep questions that we’ll look at here.
I’ll begin a short series of posts on prime numbers with several questions on the basics: What are prime (and composite) numbers, and why do they matter?