# Proof: if $n=pq$ then $p-1\mid q-1$ and $q-1\mid p-1$

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 :-)

-
You get the right spacing if you use \mid instead of |. Also "mod" is usually not italicized. – joriki Oct 25 '11 at 12:31
Thanks for \mid – ulead86 Oct 25 '11 at 12:46
I also would like to know who the author is. Carmichael numbers are cool. I would also suggest making the title of the problem more tidy so it fits on the main page. – JavaMan Oct 25 '11 at 12:48

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

-

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?

-
It's not the complete proof, it's one step in the proof of the Korselt-Theorem including Carmichael-Numbers. If n is a CMN <=> for all $p \in \mathbb{P}$ with $p \mid n$ we get $(p-1) \mid (n-1)$ – ulead86 Oct 25 '11 at 12:44
$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