P-1 consecutive numbers coprime to n

[shmounal]

a) Let an integer $n > 1$ be given, and let $p$ be its smallest prime factor. Show
that there can be at most $p − 1$ consecutive positive integers coprime to $n$.
b) Show further that the number $p − 1$ in (a) cannot be decreased, by exhibiting
$p − 1$ consecutive positive integers coprime $n$.
c) What is gcd$(p − 1, n)$?
d)Show that $2^n \not\equiv 1 (mod n)$.

I think the first part has something to with the fact that two positive integers are coprime iff they have no prime factors in common. As if there were more than $p-1$ consecutive numbers then they would have a coprime in common. Not sure how to word this convincingly!

Not sure for b). Guessing I'd say c) is $p-1$, though not sure. d).. no clue!

If you can point me in the right direction I'd appreciate it, thanks.

 

[chisigma]

a) Let an integer $n > 1$ be given, and let $p$ be its smallest prime factor. Show
that there can be at most $p − 1$ consecutive positive integers coprime to $n$.
b) Show further that the number $p − 1$ in (a) cannot be decreased, by exhibiting
$p − 1$ consecutive positive integers coprime $n$.
c) What is gcd$(p − 1, n)$?
d)Show that $2^n \not\equiv 1 (mod n)$.

I think the first part has something to with the fact that two positive integers are coprime iff they have no prime factors in common. As if there were more than $p-1$ consecutive numbers then they would have a coprime in common. Not sure how to word this convincingly!

Not sure for b). Guessing I'd say c) is $p-1$, though not sure. d).. no clue!

If you can point me in the right direction I'd appreciate it, thanks.

Considering that the number of coprimes of n is the Euler's function...

$\displaystyle \varphi(n)= n\ \prod_{p|n} (1-\frac{1}{p})$ (1)

... if $p_{0}$ is the smallest prime dividing n then is...

$\displaystyle \varphi(n)= \frac{n}{p_{0}}\ (p_{0}-1)\ \prod_{p|\frac{n}{p_{0}}} (1-\frac{1}{p})$ (2)

... and in any case the term $p_{0}-1$ is a factor of $\varphi(n)$...

Kind regards

$\chi$ $\sigma$