¿Son todos los números impares coprime a poderes de dos?

Question

Necesito elegir un número$n$ que es co-prime a un número que es un poder de dos$m = 2^b$. Me parece cierto que todos los números impares entre 1 y$m$ serán coprime a$m$, pero no puedo encontrar una prueba específica de esto en ninguna parte.

He probado esto con código de hasta un poder de 32 bits de dos$1 < b < 32$, pero eso no prueba que es siempre cierto ...

Answer 1

Piénselo de esta manera: en el típico equipo, en un tipo de datos entero (con o sin signo, independientemente de la longitud de la palabra), el bit menos significativo de un número impar es 1. Lo que significa que si se divide un número impar por 2, vas a necesitar un tipo de datos real en lugar de un tipo de datos entero.

Por ejemplo, 101 en binario (5 en decimal) dividido por 10 (2) 10.1 (2.5 en decimal). 101 dividido por 100 (4) es de 1.01, 101 dividido por 1000 (8) es 0.101... usted consigue la idea.

No sé mucho acerca de cómo los equipos de representar a los números enteros, pero el punto aquí es que si se divide un número impar número por una potencia de 2 (con un exponente entero positivo), el resultado de esa operación no puede ser considerado en un tipo de datos entero.

---

EDIT: Por alguna extraña razón que yo creía, equivocadamente, que el comentario era alguien que no era el autor de la pregunta, así que no sentí la urgencia de responder. Yo sólo tenía el objetivo de proporcionar un ángulo diferente para mirar esto, no dar una rigurosa prueba.

Pero eso es fácil de hacer, mientras que mirando a los bits de un tipo de datos entero. Si $n$ es un número impar mayor que 1, y $m$ $\alpha$ son ambos enteros positivos, que pueden ser pares o impares, buscamos encontrar $mn = 2^\alpha$. Vamos a decir $n = 2k + 1$ donde $k$ es un entero positivo.

Si $m$ es también raro, vamos, se expresa en $2j + 1$, $j$ es también un entero positivo. A continuación,$mn = 4kj + 2k + 2j + 1$, un número impar. Por lo $m$ debe ser aún después de todo, por lo $m = 2j$. A continuación,$mn = 4kj + 2j$, un número, que es lo que queremos. Pero $mn$ tiene al menos dos partes, ya que $4 > 2$$kj > j$, pero $2^\alpha$ tiene sólo uno de bits, seguido por $\alpha$ de descuento bits.

Answer 2

No sólo hasta$m$. Todos los números impares serán coprime.

Un número impar no tendrá$2$ como factor principal. Un número$m = 2^b$ sólo tendrá$2$ como factor principal. Así que cualquier número impar y cualquier$m = 2^b$ no tendrán factores primos en común. Así que serán coprime. QED.

Answer 3

Sí, eso es correcto, ya que el único factor primo de cualquier número$m = 2^b$ es$2$, mientras que cualquier número impar$n$ no tiene$2$ como factor primario . Por lo tanto, tal$m$ y$n$ no comparten factores primos, y por lo tanto son co-prime.