Prove that $\gcd(n,p-1)=1$ if $p$ is the smallest prime divisor of $n$ Let $n$ be a natural number greater than $1$, and $p$ be the smallest prime divisor of $n$.
How can I prove that $\gcd(n,p-1)=1$?
 A: Hint $\ $ By hypothesis, the prime factors of $\,n\,$ are $\,\color{#c00}{\ge p}.\,$ But the prime factors of $\,p\!-\!1\,$ are $\,\color{#c00}{< p}.$
A: Let $k=\gcd(n,p-1)$ then $k$ divides $n$ and assume that $k>1$ so by the fundamental theorem of arithmetic any prime $p'$ that divides $k$ is a prime that divides $n$ which is impossible since $p'\le k<p$ and $p$ is the smallest prime divides $n$ so $k=1$.
A: *

*Let $x_1<x_2<\dots<x_i$ be the prime factors of $n$

*Let $y_1<y_2<\dots<y_j$ be the prime factors of $p-1$

*We know that $y_j \leq p-1 < p = x_1$

*Therefore $y_1<y_2<\dots<y_j<x_1<x_2<\dots<x_i$

*Therefore $n$ and $p-1$ have no common prime factors

*Therefore $\gcd(n,p-1)=1$
A: Assume $\gcd(n,p-1)\neq 1$. Consider $q$ a prime divisor of $\gcd(n,p-1)$.
$q|\gcd(n,p-1)|n$ and as $q$ is prime, $q\ge p$. But as $q|\gcd(n,p-1)|p-1$, $q<p$. This is impossible.
A: If p is the smallest prime that divides n, then there is no smaller number that divides n: proof - assume so and let q < p divide n, then by definition q is not prime, so q has prime factors which are less than q (and therefore less than p) and since q divides n then these prime factors divide n - contradiction.
If q divides p - 1, then q < p and therefore q cannot divide n, so GCD (n, p-1) = 1.
A: The smallest prime divisor is also the smallest non-trivial divisor. Hence $p-1$ does not divide $n$ unless $p-1=1$. In either case, this means that $\gcd (n,p-1)=1$.
