Lema levantando o expoñente

Na teoría de números elemental, o lema de levantamento do expoñente (lema LTE nas siglas en inglés) proporciona varias fórmulas para calcular a valoración p-ádica ${\nu }_p$ de certas expresións de números enteiros. O lema chámase así porque describe os pasos necesarios para "levantar" o expoñente de $p$ nesas expresións. Está relacionado co lema de Hensel.

Enunciado

(Notación: $p\mid x$ lese $p$ divide a $x$, e coa barra riscada $p\nmid x$ lese $p$ non divide a $x$).

Para calquera números enteiros $x$ e $y$, un número enteiro positivo $n$, e un número primo $p$ tal que $p\nmid x$ e $p\nmid y$, cúmprense as seguintes afirmacións:

• Cando $p$ é impar:
  • Se $p\mid x-y$, entón ${\nu }_p(x^n-y^n)={\nu }_p(x-y)+{\nu }_p(n)$.
  • Se $p\mid x+y$ e $n$ é impar, entón ${\nu }_p(x^n+y^n)={\nu }_p(x+y)+{\nu }_p(n)$.
  • Se $p\mid x+y$ e $n$ é par, entón ${\nu }_p(x^n+y^n)=0$.
• Cando $p=2$:
  • Se $2\mid x-y$ e $n$ é par, entón ${\nu }_2(x^n-y^n)={\nu }_2(x-y)+{\nu }_2(x+y)+{\nu }_2(n)-1={\nu }_2\left(\frac{x^2-y^2}{2}\right)+{\nu }_2(n).$
  • Se $2\mid x-y$ e $n$ é impar, daquela ${\nu }_2(x^n-y^n)={\nu }_2(x-y)$ (dedúcese do caso xeral embaixo),
  • Corolarios:
    • Se $4\mid x-y$, entón ${\nu }_2(x+y)=1$ e daquela ${\nu }_2(x^n-y^n)={\nu }_2(x-y)+{\nu }_2(n)$.
    • Se $2\mid x+y$ e $n$ é par, daquela ${\nu }_2(x^n+y^n)=1$.
    • Se $2\mid x+y$ e $n$ é impar, daquela ${\nu }_2(x^n+y^n)={\nu }_2(x+y)$.
• Para todo $p$:
  • Se $p\mid x-y$ e $p\nmid n$, daquela ${\nu }_p(x^n-y^n)={\nu }_p(x-y)$.
  • Se $p\mid x+y$, $p\nmid n$ e $n$ é impar, daquela ${\nu }_p(x^n+y^n)={\nu }_p(x+y)$.

Xeneralizacións

O lema LTE xeneralizouse a valores complexos de $x,y$ sempre que o valor de $\frac{x^n-y^n}{x-y}$ sexa enteiro.

Esquema de proba

Caso base

O caso base ${\nu }_p(x^n-y^n)={\nu }_p(x-y)$ cando $p\nmid n$ compróbase primeiro. Pola mor de $p\mid x-y⟺x\equiv y(\mathrm{mod}p)$ ,Modelo:Bloque numerado por tanto non ten potencias de $p$ e non aporta nada na valoración.

O feito de que a fórmula de Bernoulli $x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+x^{n-3}{y}^2+\dots +y^{n-1})$ completa a proba, pois dese produto só aporta na valoración o factor $(x-y)$.

A condición ${\nu }_p(x^n+y^n)={\nu }_p(x+y)$ por $n$ impar é semellante.

Caso xeral (p impar)

Se facemos $n=p$ en (Modelo:EquationNote), muda unha condición, pois agora $p\mid n$ e por tanto

$x^{p-1}+x^{p-2}y+x^{p-3}{y}^2+\dots +y^{p-1}\equiv p{x}^{p-1}\equiv 0(\mathrm{mod}p).$

Coa mesma condición e a substitución $y=x+kp$, vía a expansión binomial, pódese mostrar que ${\nu }_p(x^p-y^p)={\nu }_p(x-y)+1$ porque (Modelo:EquationNote) é múltiplo de $p$ mais non de $p^2$. Así mesmo, ${\nu }_p(x^p+y^p)={\nu }_p(x+y)+1$ .

Entón, se $n$ se escribe como $p^{a}b$ onde $p\nmid b$, o caso base dá ${\nu }_p(x^n-y^n)={\nu }_p((x^{p^a}{)}^b-(y^{p^a}{)}^b)={\nu }_p(x^{p^a}-y^{p^a})$. Por indución en $a$,

$\begin{array}{cc}{\nu }_p(x^{p^a}-y^{p^a})& ={\nu }_p(((\dots (x^p{)}^p\dots ){)}^p-((\dots (y^p{)}^p\dots ){)}^p)\text{(exponenciación usada }a\text{ veces por termo)}\\ & ={\nu }_p(x-y)+a\end{array}$

O enunciado ${\nu }_2(x^n-y^n)={\nu }_2(x-y)+{\nu }_2(x+y)+{\nu }_2(n)-1$ cando $2\mid x-y$ demóstrase de xeito análogo.

Caso xeral (p = 2)

A proba para o caso con $p$ impar non se pode aplicar directamente cando $p=2$ porque o coeficiente binomial $(\genfrac{}{}{0ex}{}{p}{2})=\frac{p(p-1)}{2}$ é só un múltiplo enteiro de $p$ cando $p$ é impar.

No entanto, pódese demostrar que ${\nu }_2(x^n-y^n)={\nu }_2(x-y)+{\nu }_2(n)$ cando $4\mid x-y$ escribindo $n=2^{a}b$ onde $a$ e $b$ son enteiros con $b$ impar e decatándose de que

$\begin{array}{cc}{\nu }_2(x^n-y^n)& ={\nu }_2((x^{2^a}{)}^b-(y^{2^a}{)}^b)\\ & ={\nu }_2(x^{2^a}-y^{2^a})\\ & ={\nu }_2((x^{2^{a-1}}+y^{2^{a-1}})(x^{2^{a-2}}+y^{2^{a-2}})\cdots (x^2+y^2)(x+y)(x-y))\\ & ={\nu }_2(x-y)+a\end{array}$

posto que $x\equiv y\equiv \pm 1(\mathrm{mod}4)$, cada factor na diferenza de cadrados salta á forma $x^{2^k}+y^{2^k}$ que é congruente con 2 módulo 4.

A afirmación ${\nu }_2(x^n-y^n)={\nu }_2(x-y)+{\nu }_2(x+y)+{\nu }_2(n)-1$ cando $2\mid x-y$ próbase de xeito análogo.

En competicións

Problema de exemplo

O lema LTE pódese usar para resolver o problema 2020 AIME I #12:

Sexa

$n$

o número enteiro menor positivo para o cal

$149^n-2^n$

é divisíbel por

$3^3\cdot 5^5\cdot 7^7.$

Atopar o número de divisores enteiros positivos de

$n$

.

Solución. Temos en conta que

$149-2=147=3\cdot 7^2$

. Usando o lema LTE, posto que

$3\nmid 149$

nin

$2$

, pero

$3\mid 147$

, temos

${\nu }_3(149^n-2^n)={\nu }_3(147)+{\nu }_3(n)={\nu }_3(n)+1$

. Así,

$3^3\mid 149^n-2^n⟺3^2\mid n$

.

Do mesmo xeito, $7\nmid 149,2$, pero $7\mid 147$, así que ${\nu }_7(149^n-2^n)={\nu }_7(147)+{\nu }_7(n)={\nu }_7(n)+2$ e $7^7\mid 149^n-2^n⟺7^5\mid n$ .

Posto que $5\nmid 147$, os factores de 5 abórdanse observando que os residuos de $149^n$ módulo 5 seguen o ciclo $4,1,4,1$ e os de $2^n$ seguen o ciclo $2,4,3,1$, os residuos de $149^n-2^n$ módulo 5 seguen un ciclo a través da secuencia $2,2,1,0$. Así, $5\mid 149^n-2^n$ se e só se $n=4k$ para algún número enteiro positivo $k$.

Agora pódese aplicar de novo o lema LTE: ${\nu }_5(149^{4k}-2^{4k})={\nu }_5((149^4{)}^k-(2^4{)}^k)={\nu }_5(149^4-2^4)+{\nu }_5(k)$. Posto que $149^4-2^4\equiv (-1{)}^4-2^4\equiv -15(\mathrm{mod}25)$, e ${\nu }_5(149^4-2^4)=1$. Daí $5^5\mid 149^n-2^n⟺5^4\mid k⟺4\cdot 5^4\mid n$.

Combinando estes tres resultados, compróbase que $n=2^2\cdot 3^2\cdot 5^4\cdot 7^5$, que ten $(2+1)(2+1)(4+1)(5+1)=270$ divisores positivos.

Véxase tamén

Outros artigos

• Lema de Hensel.
• Último teorema de Fermat.
• Aritmética modular

Ligazóns externas

• Art of problem solving.