# Greatest common divisor

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

Let $n>4$

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

and

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

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

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

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

Quote:

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

Quote:

If n is not prime then $n=ab$ where $1< a,b . Therefore, we are able to find $a, b$ among $1, 2, ..., n-1$.
Thus, $n|(n-1)!$ and so $(n, (n-1)!)=n$.
What about $a=b$?
$n=aa$ where $1. we are able to find $a$ among $1, 2, ..., n-1$, but... and the other $a$?

Can you prove?

Thanks