2
$\begingroup$

Now I'm asking my first question to understand a specific proof:

Let $n=pq$ and $q,p \in \mathbb{P}$. Then we get $p-1\mid n-1$ and $q-1\mid n-1$, because there are prime integers mod $p$ and mod $q$. Further we get $n-1=pq-1=p(q-1)+p-1$. To this step everything is clear. Now the author says: from $p(q-1)+p-1$ it follows $q-1\mid p-1$ and $p-1\mid q-1$. I don't have a clue how he gets there. Any help is appreciated. Thanks :-)

  • 0
    I also would like to know who the author is. Carmichael numbers are cool. I would also suggest making the title o$f$ the problem more tidy so it $f$its on the main page.2011-10-25

3 Answers 3

5

This is to show that if $n=pq$ and if $p-1$ divides $n-1$, then $p-1$ divides $q-1$.

To wit, $p-1$ divides $n-1$ hence $p-1$ divides $(n-1)-(p-1)=p(q-1)$ as well. But $p-1$ and $p$ are relatively prime hence $p-1$ divides $q-1$.

2

You have a mistake somewhere. Take $p=5,q=3$ then $n=pq=15$ but $n-1=14$ is not divisible by $p-1=4$.

Who is the author?

  • 2
    Daniel, you can go back and edit your question to include relevant information2011-10-25
0

$p\!-\!1\mid\! \overbrace{pq}^n\!\!-\!1\iff p\!-\!1\mid q\!-\!1,\ $ by $ $ mod $\ p\!-1\!:\ \ \color{#c00}{p\equiv 1}\,\Rightarrow\, \color{#c00}pq\!-\!1 \equiv q\!-\!1\ \ $ QED