$\gcd(p, (p-1)!) = 1$?

Question

Let $p$ be a prime number. Prove that $\gcd(p, (p-1)!) = 1$.

I've attempted using the definition of $\gcd$ to solve this, but I haven't reached a conclusion.

Any ideas?

The only positive divisors of $p$ are $1$ and $p$. Does $p$ divide $(p-1)!$? — Brian M. Scott, Oct 14 '14 at 22:01
Wilson's theorem settles this in 1 step: http://en.wikipedia.org/wiki/Wilson's_theorem — Fixee, Oct 14 '14 at 22:07

score 1 · Answer 1 · answered Oct 14 '14 at 22:09

1

Hint: let $d=\gcd(p, (p-1)!)$. $d$ divides $p$ so $d\in \{1,p\}$. If $d\neq 1$, then $p=d|(p-1)!$. But what can you say about the greatest prime divisor of $(p-1)!$?

answered Oct 14 '14 at 22:09

mookid

28,236

score 1 · Answer 2 · answered Oct 14 '14 at 22:11

By Euclid's lemma we see that if $p|(p-1)!$ then $p|k$ for some $k\in\{1,\ldots, p-1\}$ which's a contradiction. Hence the result.

It's worth to mention that the Wilson's theorem give a more accurate result.

score 0 · Answer 3 · answered Oct 14 '14 at 22:08

0

Divisors of $p$ are $p$ and $1$. Divisors of $(p-1)!$ are $1$, $2$, ... $p-1$ and all possible multiplications of them. Considering $p$ is prime, it isn't included in set of these multiplications, so the only common number in these sets is $1$.

answered Oct 14 '14 at 22:08

Andrei Rykhalski

1,325
9
14

score 0 · Answer 4 · answered Oct 14 '14 at 22:12

0

According to the Wilson's theorem, the natural number $p$ is prime if and only if $(p-1)!\equiv -1(\mod p)$, hence $p|(p-1)!+1\Rightarrow (p-1)!+1=pk\Rightarrow pk+(-1)(p-1)!=1\Rightarrow (p,(p-1)!)=1$

answered Oct 14 '14 at 22:12

CLAUDE

2,379

$\gcd(p, (p-1)!) = 1$?

4 Answers4