$\omega(p^n - 1)$ como $n \rightarrow \infty$

Question

Aunque también me interesa el número de factores primos distintos (sin contar multiplicidad), hoy utilizo $\omega(m)$ para denotar el número de primos (positivos) (con multiplicidad) del número entero $m$ . Así $\omega(75)=3$ en este puesto. (Puede que cambie a $\omega(75)$ siendo 2 en otro post).

Qué se sabe sobre $\omega(p^n - 1)$ para un número entero fijo $p \gt 1$ y creciendo $n$ ? En $n$ es compuesto, la factorización algebraica garantiza algo como $\Omega(\omega(n))$ factores. Me interesan especialmente los casos en los que $n\lt \omega(p^n - 1)$ . No tengo una prueba, pero creo que para $p$ se puede demostrar que sólo hay un número finito de tales casos.

Si algo es conocido por $p$ primo, eso me interesaría mucho. Sigo pensando que el caso general es digno de mención, y agradecería una referencia.

Answer 1

Para fijos $p$ y cualquier $d$ los divisores primos de $\Phi_d(p)$ (polinomio ciclotómico) o bien dividen $d$ o son $1\pmod{d}$ . Así que tenemos una constante $c_p$ que satisfaga $$\omega(\Phi_d(p))\le c_p \frac{d}{\log d}$$ y así obtenemos $$\omega(p^n-1)\le c_p \sum_{d|n} \frac{d}{\log d}.$$ Siempre es inferior a $n$ para un tamaño suficientemente grande $n$ por lo que su afirmación se deduce.

Answer 2

Esto es un complemento a la respuesta de Gjergji que parece estar básicamente bien, pero hay algunos detalles que parecen faltar.

En primer lugar, observamos que $$ p^n-1= \prod_{d|n} \Phi_d(p), $$ donde $\Phi_d(p)$ son los polinomios ciclotómicos de grado $\phi(d) \leq d$ .

El hecho de que los divisores de $\Phi_d(p)$ son de la forma $kd+1$ o un divisor de $d$ (véase, por ejemplo http://number.subwiki.org/wiki/Congruence_condition_on_prime_divisor_of_cyclotomic_polynomial_evaluated_at_an_integer ) es suficiente para obtener

$$\omega(\Phi_d(p)) \leq c_p \frac {d} {\log d}$$

para el número de factores primos que tienen la forma $kd+1$ . Esto se debe a que, en particular, deben ser mayores que $d$ y $d^{d \log p/\log d}=p^d \geq \Phi_d(p)$

Así que por la respuesta de Gjergji es suficiente demostrar que el número de factores primos (contados con multiplicidad) $q$ tal que $q|n$ que divide $p^n-1$ no son demasiados. También es suficiente considerar los primos $q$ decir menos de $p^2$ por un argumento similar al anterior (podemos tener como máximo $n/2$ principales factores del tamaño $p^n$ si todos los factores primos son mayores que $p^2$ ).

Está claro que existe alguna constante $m_0$ tal que para todos los primos $q<p^2$ tenemos que $q^{m_0}$ no divide $p^{q-1}-1$ . De ello se deduce que si $n$ tiene factores primos de orden como máximo $m_1$ entonces $q^{m_0+m_1}$ no divide $p^n-1$ . Por tanto, el número de factores primos es como máximo $p^2 (m_0+m_1)$ donde $n \geq 2^{m_1}$ . Esto nos da que el número de factores primos que divide a $n$ y son inferiores a $p^2$ es $O(\log n)$ y que son insignificantes

Answer 3

Hagamos un poco de matemática elemental. Teoría de números estilo olimpiada. Todo lo que necesitamos mostrar es que para cada primo fijo $q$ , $v_q(p^n-1)=o(n)$ . Desde $gcd(p^n-1,p^m-1)=p^{gcd(n,m)}-1$ si $n=n_0$ es la menor potencia tal que $v_q(p^n-1)>v_q(p-1)$ entonces cada $n$ que satisfaga esta desigualdad debe ser divisible por $n_0$ . Entonces el Lemma del exponente elevador da $v_q(p^n-1)\le C(p,q)+v_q(n)\le C(p,q)+\log n$ . El fin.