Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

1 Answer 1

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

 
discard

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.