# Greatest common divisor

• Dec 3rd 2008, 11:23 AM
asub1
Greatest common divisor
Hi.
Can anybody prove that?

Let \$\displaystyle n>4\$

\$\displaystyle GCD(n, (n-1)!)=1 \Longleftrightarrow{} n\$ its prime.

and

if \$\displaystyle n\$ its not prime \$\displaystyle \Longrightarrow{} GCD(n, (n-1)!)=n\$

Thanks
• Dec 3rd 2008, 03:07 PM
ThePerfectHacker
Quote:

Originally Posted by asub1
\$\displaystyle GCD(n, (n-1)!)=1 \Longleftrightarrow{} n\$ its prime.

This should be clear. If \$\displaystyle n\$ is prime then \$\displaystyle 1,2,3...,n-1\$ show no non-trivial factors with \$\displaystyle n\$. Thus, \$\displaystyle (n,(n-1)!)=1\$.

Quote:

if \$\displaystyle n\$ its not prime \$\displaystyle \Longrightarrow{} GCD(n, (n-1)!)=n\$
If \$\displaystyle n\$ is not prime then \$\displaystyle n=ab\$ where \$\displaystyle 1<a,b<n\$. Therefore, we are able to find \$\displaystyle a,b\$ among \$\displaystyle 1,2,...,n-1\$.
Thus, \$\displaystyle n|(n-1)!\$ and so \$\displaystyle (n,(n-1)!)=n\$.
• Dec 4th 2008, 01:08 AM
asub1
Hi!

Quote:

If n is not prime then \$\displaystyle n=ab\$ where \$\displaystyle 1< a,b <n\$. Therefore, we are able to find \$\displaystyle a, b\$ among \$\displaystyle 1, 2, ..., n-1\$.
Thus, \$\displaystyle n|(n-1)!\$ and so \$\displaystyle (n, (n-1)!)=n\$.