Intuitive Approach to Wilson's Theorem

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

An Intuitive Guide To Exponential Functions & E

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

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"

Coprime, aka. Relatively Prime

Two numbers are coprime (relatively prime) if they have no factors in common.
I thought this image from Wikipedia was a good visual way of seeing it:

Figure 1. The numbers 4 and 9 are coprime because the diagonal does not intersect any other lattice points

Subfactorial

I thought this was a good way of explaining it:
In practical terms, subfactorial is the number of ways of putting n letters into n envelopes (one in each envelope) with none in its correct envelope.

Pi

This is probably the simplest explanation of Pi that I have ever seen:

Mock Theta Functions

Sum of Series

sum of odd integers < 2n = n²

sum of all integers = n(n+1)/2

Pascals' Cototients

Similar to yesterdays' post, this one is based off the totients of the values in Pascal's triangle.. but this time, we are displaying the Cototients (n - totient(n))...

Pascal's Totients

I was trying to figure out new ways to look at Pascals' Triangle today, and decided to look not at the actual binomial coefficients, but at the Euler Totients of them. Take a gander.

Pascal and Binomial Coefficients

I realized that I never really showed how Pascal's Triangle is related to the Binomial Coefficients... So here we go:

(x+1)0 = 
1

(x+1)1 =
1x + 1 =
1 1

(x+1)2 =
(x+1)(x+1) = 
x*x + x*1 + 1*x + 1*1 = 
1x2 + 2x + 1 = 
1 2 1

(x+1)3 =
(x+1)(x+1)(x+1) = 
((x+1)(x+1))(x+1) = 
(1x2 + 2x + 1)(x+1) = 
(1x2*x + 1x2)+(2x*x + 2x*1)+(1*x + 1*1)= 
1x3 + 1x2 + 2x2 + 2x + x + 1 = 
1x3 + 3x2 + 3x + 1 =
1 3 3 1


(x+1)4 =
(x+1)(x+1)(x+1)(x+1) =
((x+1)(x+1)(x+1))(x+1) = 
(1x3 + 3x2 + 3x + 1)(x+1) =
(1x3*x + 1x3*1)+(3x2*x + 3x2*1)+(3x*x + 3x*1)+(1*x + 1*1) =
1x4 + 1x3 + 3x3 + 3x2 + 3x2 + 3x + 1x + 1 =
1x4 + 4x3 + 6x2 + 4x + 1 = 
1 4 6 4 1

A Modded Pacal Triangle

As you generate very large Pascal Triangles, the numbers quickly get out of control. If you are planning on modding the values after obtaining them, why not mod them first?

Here you see an example of doing a mod5 before writing the number down... So, for example, the middle element on Row#4 is 1 because (3+3)%5 = 6%5 = 1... Now, you can use the number 1 for further rows instead of the original number 6.

Binary Representation of Pascal's Triangle

To look like this, one thing you might do is work out all the values of the previous lines and then mod them to determine whether they should be highlighted or not.

Yet another way might be to just keep track of whether the values above are 1 or 0, and realize that the next one down is only 0 if both the parent hexes are 1.

But, how about a way to do it without any regard to previous rows? This method is quite simple...

Let's say you want to examine nCr (n=row, r=col)... say, 5C2 (10 if you look at the image)...

How do we do it? First, write down the binary value of n and r.

n (5) = 101

r (2) = 010

Now, if ANY digit in r is larger than the corresponding digit in n, it is even. Otherwise, it is odd.

Looking at our example, we compare:

	bits
	2	1	0
n	1	0	1
r	0	1	0
r[1] is higher than n[1] so it is even

So, to determine if any point in Pascals' Triangle is odd/even, you just have to compare the binary representation of the row and column. :)

Twin Primes

So as I rewrite my Balanced Ternary (ī,0,1) library once again, something occurs to me...

While it is not visually obvious which numbers are multiples of two, we do know that all multiples of 3 end in 0. Since no prime (except 3) can be a multiple of 3, that means that all primes are going to end in ī or 1. Well, since we know all primes are odd, that also means that the specific number with a 0 ending would have also been a multiple of 2. IE: The number ending in 0 would have been a multiple of 6.

Where am I going with this? Well, let's look at the first few multiples of 2*3
6 - 5 and 7 are twin primes
12 - 11 and 13 are twin primes
18 - 17 and 19 are twin primes
24 - 23 and 25... nope, not that one (23 is prime though, other is 5²)
30 - 29 and 31 are twin primes
36 - 35 and 37... nope, not that one (37 is prime though, other is 5*7)
42 - 41 and 43 are twin primes
48 - 47 and 49... nope, not that one (47 is prime though, 49 is 7²)
54 - 53 and 55... nope, not that one (53 is prime though, other is 5*11)
60 - 59 and 61 are twin primes
66 - 65 and 67... nope, not that one (67 is prime though, other is 5*13)
72 - 71 and 73 are twin primes
80 - 79 and 81... nope, not that one (79 is prime though, 81 is 9²)

well obviously that wasn't the "correct solution"...

let's start with a simple question - did we miss any twin primes?
well we miss (3,5) - but that could just be because we were specifically looking for multiples of 6.
other than that, we did not skip any twin primes

what about those 'extra' entries?
well some are when we have squares (5², 7², 9²)
the others are 5*{7,11,13}
could be a pattern there... partial one anyways...

let's look at it from another aspect... what primes did we miss?
obviously anything below 6 since we started with multiples of 6
other than that, we got all primes...
and 6 extra values below 82... so about 7% too many

it has to become less usable as we get higher, doesn't it?
600 - 599 and 601 are twin primes
606 - 607 is prime
612 - 613 is prime
618 - 617 and 619 are twin primes
624 - (neither 623 or 625 are prime)
630 - 631 is prime
636 - (neither 635 or 637 are prime)
642 - 641 and 643 are twin primes
648 - 647 is prime
652 - 653 is prime
660 - 659 and 661 are twin primes

and no primes are missing (though a couple extras)

Prime Numbers, Assumptions and Thoughts

Prime numbers have been a challenge to people for a very long time. If they are something that we still can't write an equation for, perhaps it is time to challenge our assumptions about these fascinating and extremely important numbers.

First, it is commonly believed that there is no pattern to prime numbers. Research studied under this belief might very well be simply falling prey to self-fullfilling prophecy. We know that prime numbers do indeed have a pattern. How? Because color-coding a Pascal Triangle to look like a Sierpinski Gasket shows that prime numbers form perfect fractals, while composite numbers show overlapping fractcals. I discussed this a little while ago. Using this method, with just a couple sentences of explanation, ANYONE can look at a picture (mod some number) and tell you if it is a prime number or not (primes look clean, composites look cluttered). The pattern is visually obvious.

Second, let's tackle the concept that '1' is not a prime number... Some people will tell you that '1' isn't prime because it doesn't fit the rules. Others because it isn't convenient. Still others say it was due to the Greeks thinking number games weren't as challenging with it. Hell, you are probably wondering why we even care... Simple: If '1' IS a prime number, then all the equations that don't quite work change... the math changes... We get rid of "except 1" or ">=2" type of exceptions... but most importantly, because it would force us to look at things differently -- which is what we desperately need if we are going to 'solve' primes.

So, what about the argument that it doesn't fit the rules? What is the definition of a prime number? Generally, people assume it is "any number greater than 1 that has only 1 and itself as factors".. So 1*3 is prime because no other number is a factor. 1*4 is not prime because 2 is a factor. 1*1 has no other factors, therefore it should be considered prime. But, you also see why people have a problem with it. Because it is also a square ;) They always say "1 and itself"... Well, under that definition '1' should be prime. The only reason they say it isn't is because they add the clause "greater than 1" or "except 1" to the rule. Occam's razor fans should be well aware of the problem here. You don't add a single exception (for a number that would otherwise work) just because you don't like or understand it.

You are probably still wondering why we care... Let's say you are writing an equation... f(n)=nth prime. Well, if '1' is prime, then all the current attempts are actually doing f(n)=(n+1)st prime... thus patterns may be easier to see if we quit assuming 1 can't be prime.

What other assumptions do we have? Primes get further and further apart... Not true... No matter how high you go, there will be twin primes. This tells us that twin primes are not a special case or exception -- but are in fact part of the pattern. And don't forget what we said earlier -- it is a fractal -- so it repeats forever.

In fact, the whole concept that there are 'types of primes' is simply a misnomer. Each type of prime is simply a subset of the fractal.

Slashdot | Largest Twin Prime Yet Discovered

The Twin Internet Prime Search and PrimeGrid have recently discovered the largest known twin prime. A twin prime is a pair of prime numbers separated by the integer two. The pair discovered on January 15th was 2003663613 * 2195,000 ± 1. The two primes are 58,711 digits long. The discoverer was Eric Vautier, from France.