1

If $x$ is prime, $\frac{(x-1)!-(x-1)}x$ is always an integer.

Is there a way to explain this using modern algebra? I feel as if though it has to do with the concept of relatively prime or $\gcd$s, but I'm not exactly sure what is happening. I can verify it is true by plugging in a bunch of different primes and verifying that it works. I want to however explain this using algebra. I was thinking maybe divisor algorithm would work too. Thanks.

Parcly Taxel
  • 103,344
rain
  • 793

1 Answers1

1

Take Wilson's theorem: $$(p-1)!\equiv-1\bmod p$$ Of course, we can subtract $p$ from the LHS and the congruence will not change: $$(p-1)!-p\equiv-1\bmod p$$ This is equivalent to $$\frac{(p-1)!-p+1}p=\frac{(p-1)!-(p-1)}p\in\mathbb Z$$ and the claim is proved.

Parcly Taxel
  • 103,344
  • I see. I get it now. So could you just explain the pairing again in Z_5 x and how that shows the product of its elements is -1 mod p? I am starting to understand better. – rain Feb 24 '18 at 04:30
  • @rain OK. $\mathbb Z_p^×$ is the multiplicative group associated with the (odd) prime $p$, which has $p-1$ elements. Each element in this group has an inverse element, and the product of an element and its inverse is the identity of 1. Only 1 and $-1$ are their own inverses, though. These multiply to produce $-1\bmod p$. You have a whole bunch of 1's, but only one $-1$; it follows that the product of all the elements in $\mathbb Z_p$ excluding 0 is $-1$. – Parcly Taxel Feb 24 '18 at 04:33
  • Thanks! So for Z5 x only 1 is its own inverse as 1*1=1 and 1 is the identity here. So how would this work ( I like understanding concrete cases). But wouldnt the inverse of 2 but 1/2 which is not in Z5 x? – rain Feb 24 '18 at 04:36
  • @rain Ah! This is where most newcomers trip up. The inverse of 2 in $\mathbb Z_5^×$ can be written as $\frac12$, but this is considered equivalent to 3, since $2\cdot3\equiv1\bmod5$. The only reason that guarantees an inverse for all elements in $\mathbb Z_p^×$ (and the existence of division) is the primality of $p$. Ultimately, this is the starting point for a whole sub-field of number theory: [tag:modular-arithmetic]. – Parcly Taxel Feb 24 '18 at 04:38
  • Got it. Thanks. – rain Feb 24 '18 at 04:42