Gcd, Fermat little theorem and Euler function

Question

Hi I'm stuck with two questions:

(1). Prove that if $a^{n-1}\equiv 1 \pmod n$ then $a$ and $n$ are relatively prime.

looks like Fermat little theorem but I know this theory works on prime numbers so I tried to prove this using Euler function but I don't think this is the correct way.

(2). $p$ is prime number, prove $p$ do not divide $2^p-1$.

Should I prove this using induction? I'm pretty sure there is a better way.

Answer 1

$(1)$

If $a^{n-1}\equiv1\pmod n, a^{n-1}=1+r\cdot n$ where $r$ is some integer

If $(a,n)=d, d$ divides $a^{n-1}-r\cdot n$ if $n-1\ge1$

But $a^{n-1}-r\cdot n=1$

$\implies d$ divides $1\implies d=1$

$(2)$

If prime $p>2, (2,p)=1\implies 2^{p-1}\equiv1\pmod p$ using Fermat's little theorem

$\implies 2^p\equiv2\pmod p\implies 2^p-1\equiv1\pmod p$

---

Alternatively, $2^p-1=(1+1)^p-1=1+\sum_{1\le r\le p-1}\binom p r$

But $p$ divides $\binom p r$ for $1\le r\le p-1$

Answer 2

Hints:

1. More generally, if $ab\equiv 1\pmod n$, we can conclude that $a$ is coprime to $n$.
2. $p\,|\,2^{p-1}-1\ =:A$, then $2^p-1=2A+1$.

Answer 3

Hint:

$a^{n-1}\equiv 1 (\mod n)$. When is this true?

Euler function is $a^{\phi(n)}\equiv 1(\mod n)$.

$\phi(n)=n-1 \implies n$ is a $prime$.