3

Wilson's Theorem states (for $p>1$)

$$p\;\text{is prime} \quad\iff\quad(p-1)! = -1 \bmod p$$

I was asked the following:

Explain the difference in reducing modulo $p$ after each multiplication needed to find $(p–1)!$ or reducing modulo $p$ once after end of calculations of $(p–1)!$.

But I don't understand what that means.

Say we want to find if $5$ and if $8$ are primes. Here is how I would do it:

  • $p = 5$ $$(5-1)! = 4! = 24$$ $$24 \bmod 5 = -1 \bmod 5$$ Thus, $5$ is prime.

  • $p = 8$ $$(8-1)! = 7! = 5040$$ $$5040 \bmod 8 = 0 \neq -1 \bmod 8$$ Thus, $8$ is not prime.

How does this relate to reductions?

Thank you.

Blue
  • 75,673
justanothertechdude
  • 123
  • 3
    If you keep "reducing modulo $p$" at each stage of the calculation you keep the numbers small. – Angina Seng Dec 22 '19 at 03:00
  • 1
    Welcome to Math SE. I believe "reducing mod $p$" means to change any value $\ge p$ to the corresponding value between $0$ and $p-1$, inclusive, that the value corresponds to modulo $p$. For example, you have $12$ would become $2$ modulo $5$ since $12 \equiv 2 \pmod 5$. – John Omielan Dec 22 '19 at 03:00
  • Can you please explain with an example I dont follow. – justanothertechdude Dec 22 '19 at 03:08
  • 1
    For instance, how would you check if $1033$ is prime? –  Dec 22 '19 at 03:17
  • Hi Gae, thank you for asking me that, I realise now I dont actually know how to do that, from my understanding I think it has something to do with inverses and groups. – justanothertechdude Dec 22 '19 at 03:29

2 Answers2

3

$7!\equiv\color{blue}{7\times6}\times5\color{maroon}{\times4\times3\times2}\equiv\color{blue}{42}\times5\color{maroon}{\times4\times3\times2}\equiv\color{blue}2\times5\times\color{maroon}{4\times3\times2}\equiv10\times\color{maroon}{4\times3\times2}\equiv$

$2\times4\times3\times2\equiv8\times3\times2\equiv0\pmod8$.

Or $7!\equiv\color{blue}{2\times3}\times4\times\color{maroon}{5\times6\times7}\equiv\color{blue}6\times4\times\color{maroon}{5\times6\times7}\equiv24\times\color{maroon}{5\times6\times7}\equiv0\times\color{maroon}{5\times6\times7}$

$\equiv0\pmod8.$

J. W. Tanner
  • 60,406
1

The difference is, you'll deal with a possibly huge number if you let it go too far. To check if 101 is prime by doing mod once at the end, has you deal with the number: 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

a 158 digit number.

Setting up smallest magnitude equivalents like so:

1 2 3 4 5 6 7 8 9 10

11 12 13 14 15 16 17

18 19 20 21 22 23 24

25 26 27 28 29 30 31

32 33 34 35 36 37 38

39 40 41 42 43 44 45

46 47 48 49 50 -50 -49

-48 -47 -46 -45 -44 -43 -42

-41 -40 -39 -38 -37 -36 -35

-34 -33 -32 -31 -30 -29 -28

-27 -26 -25 -24 -23 -22 -21

-20 -19 -18 -17 -18 -15 -14

-13 -12 -10 -9-8-7-6

-5 -4 -3 -2 -1

You'll never deal with a number of absolute value, more than 2500 reducing at each step. Moreover, you can square the result halfway.

  • $394290-367961=26329$ digits saved using this equivalence by 87473 before a final mod step for example. –  Dec 22 '19 at 14:42
  • the comment example I gave runs about 6 times faster than it's compute then mod counterpart. –  Dec 23 '19 at 16:13
  • and the squaring version halves again –  Dec 24 '19 at 12:21