Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ π -¹ ² ³ °

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

**JaneFairfax****Member**- Registered: 2007-02-23
- Posts: 6,868

This is something Ive just read about in H.E. Roses *A Course in Number Theory*. The proof is remarkably simple.

*Last edited by JaneFairfax (2009-03-29 11:36:46)*

Offline

**JaneFairfax****Member**- Registered: 2007-02-23
- Posts: 6,868

The proof relies on the multiplicative properties of the sigma function above.

Offline

**JaneFairfax****Member**- Registered: 2007-02-23
- Posts: 6,868

We have this interesting little result:

[align=center]

[/align]The proof is only a few lines long. Also:

*Last edited by JaneFairfax (2009-03-31 10:37:26)*

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

That

makes it easy to compute the phi function for any integer n, so long as you know its prime factorization.

"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."

Offline

**JaneFairfax****Member**- Registered: 2007-02-23
- Posts: 6,868

Offline

**JaneFairfax****Member**- Registered: 2007-02-23
- Posts: 6,868

Offline

**Daniel123****Member**- Registered: 2007-05-23
- Posts: 663

Nice

I like the combinatorial proof of Fermat's Little Theorem, which considers the number of bracelets that can be made from 'p' beads of 'a' different colours.

Offline

**JaneFairfax****Member**- Registered: 2007-02-23
- Posts: 6,868

I like the Galois-theory version of Fermats little theorem:

Ive never seen it stated like this myself so I claim originality for the statement of Fermats little theorem in this form.

*Last edited by JaneFairfax (2009-04-02 02:31:06)*

Offline

**JaneFairfax****Member**- Registered: 2007-02-23
- Posts: 6,868

Treating as a polynomial over has the advantage of enabling us to prove Wilsons theorem!

Now, Fermats theorem in the language of Galois theory means this:

Putting

gives

If

, we get ; if , the same equation is true as .This proves Wilsons theorem as my friend

http://z8.invisionfree.com/DYK/index.php?showtopic=831

*Last edited by JaneFairfax (2009-04-03 12:17:38)*

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

Wilson's theorem is a nice result, and gives a good necessary and sufficient condition for prime numbers. It is however computationally inefficient for primality testing.

"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."

Offline

**JaneFairfax****Member**- Registered: 2007-02-23
- Posts: 6,868

Wilsons theorem appears to be something not many people try to make use of.

For example, http://www.mathhelpforum.com/math-help/ … ility.html.

Offline

Pages: **1**