# greatest common divisor of p-1 and q-1 [closed]

Hi there,

Can we say that if $p$ and $q$ are distinct prime number diving $n$

$\Omega(gcd(p-1,q-1)) \leq \Omega(n)$

Where $\Omega(n)$ denotes the number of prime powers dividing $n$

Best rahmi

-

## closed as too localized by Gjergji Zaimi, Franz Lemmermeyer, Bill Johnson, S. Carnahan♦Mar 18 '11 at 16:47

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

No: let $p=13$, $q=37$ and $n=pq=481$. Then $\Omega((p-1,q-1))=\Omega(12)=3$ while $\Omega(n)=2$. – Thomas Bloom Mar 18 '11 at 9:44

No: take $n=211*2311$, $p=211, q=2311$. In fact there is no bound of the L.H.S. in terms of the R.H.S. in your inequality. Take any sequence of primes $p_1,...,p_s$. Let $a=p_1\cdot...\dot p_s$. By Dirichlet theorem there are two primes $p=ak+1, q=am+1$, $k < m$. Let $n=pq$. Then $\Omega(n)=2$ while $GCD(p-1,q-1)$ is divisible by $p_1,...,p_n$, so $\Omega(GCD)\ge n$.