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

  • 1
    You get the right spacing if you use `\mid` instead of `|`. Also "mod" is usually not italicized.2011-10-25
  • 0
    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.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?

  • 0
    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)$2011-10-25
  • 1
    Note that stating this in your question itself will help you get helpful answers.2011-10-25
  • 0
    I know, sorry for the inconvenience, I'll be more specific nexttime, I promise2011-10-25
  • 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