1
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

$(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$

$\endgroup$
0
$\begingroup$

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$.
$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ it does not necessarily imply $\phi(n)=n-1$. It implies that $ord_na$ divides $(\phi(n),n-1)$ For example, $a=8,n=9$ $\endgroup$ – lab bhattacharjee Apr 3 '13 at 15:24
  • $\begingroup$ Can you give some examples for that? $\endgroup$ – Inceptio Apr 3 '13 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.