Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

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

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

share|improve this answer

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