Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 5 down vote accepted

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.

share|cite|improve this answer
yes, thats true. Then I have to check my script again, perhaps i forgot one or two conditions... Thanks a lot – ulead86 Nov 2 '11 at 11:35

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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