The other day I stumbled across something, only later to realize that it was Wilson's Theorem. Since the approach used to find it in the first place was more of a 'common-sense' approach than what you usually encounter for it, I thought I would go ahead and present it.

Let's look at two examples.... For both, what we are looking for is:

(n-1)! % n ≡ (n-1) mod n; iff n is prime

Example 1: Composite Numbers

Let's try to determine whether '10' is prime (which we know it isn't but that just makes the example easier to follow)...

(n-1)! is 1*2*3*4*5*6*7*8*9

when we mod it by 10, what we are really saying is to "find missing factors of 10"

since both 2 and 5 are in the list, the end result will be 0*

ie: (10-1)! % 10 ≡ 0 mod 10

Example 2: Prime Numbers

Let's try to determine whether '11' is prime

(n-1)! is 1*2*3*4*5*6*7*8*9*10

when we mod by 11, what we are really saying is to "find missing factors of 11"

since 11 is not in the list, the number is prime and the end result is 10 (or -1)

ie: (11-1)! % 11 ≡ 10 mod 11

or: (11-1)! % 11 ≡ -1 mod 11

* It appears that the only composite number to NOT result into congruency with 0 is '4'

(4-1)! % 4 ≡ 2 mod 4

I believe this is because it is 2-squared and it 2-away from it... thus since we get further away as we go on, it won't happen again.

Unfortunately, this didn't end up being nearly as clear as my first draft did, but let's try to make the useful bit clear here... directly from Wilson's theorem:

(n-1)! % n ≡ -1 mod n; iff n is prime

or

(n-1)! % n = (n-1) mod n; iff n is prime

or... to put it into Windows Calculator speak:

[type in some number][M+][-][1][=][n!][mod][MR][=]

if the result is equal to [MR]-1 then it is prime

otherwise the result will be 0 (or '2' for n=4) and the number is composite/non-prime

## 27 July 2007

## 20 July 2007

### An Intuitive Guide To Exponential Functions & E

Fairly simple explanation of what 'e' is and how it works.

## 15 July 2007

### Wikipedia: Mental Arithmetic

I stumbled upon this today, and thought I would share. Some interesting stuff in there.

We really should start teaching kids mental arithmetic at an early age rather than the "show your work or get an F"

We really should start teaching kids mental arithmetic at an early age rather than the "show your work or get an F"

Subscribe to:
Posts (Atom)