$2^k$ no es divisible por 5

Question

En el Arte de la Programación Informática de Knuth, Volumen 1, se afirma sin demostración que $2^k$ no es divisible por 5 (respuesta a la pregunta 10, sección 1.2.2). Puedo construir una prueba corta, pero ¿qué intuición estoy perdiendo que hace que esto sea tan obvio?

Answer 1

La forma más fácil es darse cuenta de que el único factor primo de $2^k$ es 2, mientras que necesita tener $5$ como factor primo para ser divisible por 5.

También puedes comprobar que todas las potencias de 2 terminan en $2,4,8$ o $6$, lo que significa que nunca terminan en $0$ o $5, de ahí la prueba.

Answer 2

Dado que $5$ es primo, tendría que aparecer en una factorización prima de cualquier número que divida... ¡pero ya conoces una factorización prima de $2^k$ sin $5$!

Answer 3

Es una consecuencia inmediata de la unicidad de la factorización primaria $\,2^k = 2\cdot 2\,\cdots\, 2$

Más simplemente $\ \color{#C00}5\mid \color{#C00}{2n}\, \Rightarrow\, \color{#C00}5\mid (\color{#c00}5n - 2\!\cdot\! \color{#c00}{2n}) = n.\,$ Por inducción $\, 5\mid 2^km \,\Rightarrow\, 5\mid m.$

Ese es un caso especial del Lema de Euclides $\, a\mid bc\,\Rightarrow\, a\mid (a,b)c,\, $ el caso $\,(a,b) = 1.$ El Lema de Euclides sigue inmediatamente de la identidad de Bezout para el mcd $\,(a,b) = ja+kb\,$ para algunos $\,j,k\in\Bbb Z.\,$ Por el caso especial de $\,a\,$ primo en el Lema de Euclides, $\,p\mid bc\,\Rightarrow\, p\mid b\,$ o $\,p\mid b,\,$ ya que $\,p\nmid b\,$ $\Rightarrow$ $\,(p,b)=1,\,$ entonces $\,p\mid bc\overset{\rm Euclid}\Rightarrow p\mid(p,b)c = c.\,$ Esta Propiedad del Divisor Primo proporciona la unicidad de las factorizaciones primarias, ya que permite emparejar y cancelar primos en cualquier par de factorizaciones primarias de un entero.

Answer 4

Si $p$ es primo entonces $p\mid k\times m$ implica que $p\mid k$ o $p\mid m. Aplicando (y repitiendo) en $5\mid 2^n$ lleva a $5\mid 2$ lo cual no es cierto.