## Sunday, 15 June 2008

### Primes

You should know already, but in case you don't, prime numbers are numbers (positive whole numbers) that are divisible only by themselves and one. Any other number is a factor. A factor is made up of the product of a series of prime numbers. There are only Primes and Factors in the whole number series (called N but with a double lined middle bar)

If it's not a prime, it's a factor.

31 is prime. 32 is not (2x2x2x2x2). 33 is not (11x3). 34 is not (17x2).

one intersting thing to do with factors includes finding their greatest common divisor, and lowest common multiple (a kind of hand in had calculation)

the GCD( 32, 34 ) is 2 as 2 is the largest number that can divide both 32 and 34 without leaving a fraction.
the GCD( 12, 18 ) is 6. You can see this by checking the factors of 12 (2,2,3), and the factors of 18 (2,3,3) and seeing that the common factors (2,3) produce 6.

the LCM( 12,18 ) is 36. this is the smallest number that the two values can be multiplied to using only whole numbers. use 12x3 or 18x2 to get 36.
notice the similarity of the solution?
LCM( x,y ) = x * y / GCD( x,y )
or, another way of thinking about it is that you only include the common factors in the GCD, and in the LCM you inlcude all factors, but only the common factors once. (dividing by the GCD effectively removes the common factors).

some factors have a GCD(x,y) of 1. These are co-prime. Neither number needs to be prime, for example, consider 8 and 9. the only factor they share is 1, their least common multiple is 72.

This property can be used in creating pseudorandom sequences like mentioned in an earlier post. The important thing to remember is that the two values share no factors. Some sequences don't have very good coverage though, look at the example below.

start at 1
1*8 mod 9 is 8
8*8 mod 9 is 1

start at 2
2*8 mod 9 is 7
7*8 mod 9 is 2

start at 3
3*8 mod 9 is 6
6*8 mod 9 is 3

start at 4
4*8 mod 9 is 5
5*8 mod 9 is 4

so, you can make a sequence, but be careful how it loops around, and be sure it has a good long sequence by hand checking it.