# Modular Arithmetic Proof

**URL:** <https://boards.straightdope.com/t/modular-arithmetic-proof/665444>\
**Category:** Factual Questions\
**Created:** [August 5, 2013, 10:20pm UTC](https://boards.straightdope.com/t/modular-arithmetic-proof/665444 "2013-08-05T22:20:51Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![SC2Maar](https://avatars.discourse-cdn.com/v4/letter/s/e79b87/32.png) [@SC2Maar](https://boards.straightdope.com/u/SC2Maar)\
**Post date:** [August 5, 2013, 10:20pm UTC](https://boards.straightdope.com/t/modular-arithmetic-proof/665444/1 "2013-08-05T22:20:51Z")

</div>

I’m doing a self study of math, and I encountered some rules.

[First](http://i.imgur.com/bO2AqaY.gif)

[Second](http://i.imgur.com/qbxGHMc.gif)

These are interesting rules, and I’d like to know the proofs of them.

Thanks!

---

<div class="post-metadata">

**Author:** ![Giles](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/giles/32/60_2.png) [@Giles](https://boards.straightdope.com/u/Giles)\
**Post date:** [August 5, 2013, 10:57pm UTC](https://boards.straightdope.com/t/modular-arithmetic-proof/665444/2 "2013-08-05T22:57:39Z")

</div>

What is a “primary number”? (It’s in both pages linked in the OP.) Is this a nonstandard term for “prime number”?

---

<div class="post-metadata">

**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\
**Post date:** [August 5, 2013, 11:01pm UTC](https://boards.straightdope.com/t/modular-arithmetic-proof/665444/3 "2013-08-05T23:01:07Z")

</div>

Yeah, it means “prime”. Or at least, I’ve seen proofs of both of those statements with “prime” in the place of “primary”.

---

<div class="post-metadata">

**Author:** ![Topologist](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/topologist/32/3208_2.png) [@Topologist](https://boards.straightdope.com/u/Topologist)\
**Post date:** [August 5, 2013, 11:11pm UTC](https://boards.straightdope.com/t/modular-arithmetic-proof/665444/4 "2013-08-05T23:11:16Z")

</div>

The first is [Fermat’s Little Theorem](http://en.wikipedia.org/wiki/Proofs_of_Fermat%27s_little_theorem) and the second is [Wilson’s Theorem](http://en.wikipedia.org/wiki/Wilson%27s_theorem). See those references for proofs.

---

<div class="post-metadata">

**Author:** ![Hari\_Seldon](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/hari_seldon/32/5173_2.png) [@Hari\_Seldon](https://boards.straightdope.com/u/Hari_Seldon)\
**Post date:** [August 6, 2013, 12:43am UTC](https://boards.straightdope.com/t/modular-arithmetic-proof/665444/5 "2013-08-06T00:43:38Z")

</div>

Standardly, “primary” ought to mean a power of a prime. (A primary ideal is, as a first approximation, a power of a prime ideal.) But those two theorems are valid only for actual primes.

As for proofs, well, this is not the place for this (I assume the references are), but they both depend on the fact that when p is a prime, the numbers 1,2,…,p-1 are a group under multiplication mod p. Fermat’s little theorem holds for any group, while Wilson’s theorem follows from the fact that p-1 is the only element of order 2.
