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
1
-
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$– Thomas BloomMar 18, 2011 at 9:44
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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$.