1
$\begingroup$

I have one more question:

Let $n=pq$ with $p,q \in \mathbb{P}$, then we have $p-1 \mid n-1$ and $q-1 \mid n-1$. I don't understand the reason the author tells me: "because there are multiplicative groups of integers modulo $p$ and modulo $q$." Is there any way to proof the existence of the prime integers?

Any help is appreciated.

1 Answers 1

4

This just is not true. Let $q=3$, $p=5$ and $n=3\cdot 5 =15$. Certainly $p-1$ does not divide $n-1$ as $4$ does not divide $14$.

Another example is $q=5$, $p=7$, $n=35$. Then neither of $p-1|n-1$ or $q-1|n-1$ hold.

When is it true?: I claim that if $n=pq$ where $p,q$ are primes, and both $p-1|n-1$, $q-1|n-1$ hold, then we must have $q=p$.
Proof: Notice that we can write $n-1=pq-1=p-1+p(q-1).$ This means that if $p-1|n-1$, since $p$ and $p-1$ are relatively prime, we must have $p-1|\left(p-1+p(q-1)\right)\Rightarrow p-1|q-1.$ By symmetry, if $q-1|n-1$ as well then we have $q-1|p-1$. Hence they both divide each other so $q-1=p-1$, and we see they are equal.

  • 0
    yes, thats true. Then I have to check my script again, perhaps i forgot one or two conditions... Thanks a lot2011-11-02