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

  • 2
    $\begingroup$ No: let $p=13$, $q=37$ and $n=pq=481$. Then $\Omega((p-1,q-1))=\Omega(12)=3$ while $\Omega(n)=2$. $\endgroup$ Mar 18, 2011 at 9:44

1 Answer 1


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


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