Are all odd numbers coprime to powers of two?

Not just up to $m$. All odd numbers will be coprime.

An odd number will not have $2$ as a prime factor. A number $m = 2^b$ will only have $2$ as a prime factor. So any odd number and any $m = 2^b$ will have no prime factors in common. So they will be coprime. QED.


Think about it this way: in your typical computer, in an integer data type (signed or unsigned, regardless of word length), the least significant bit of an odd number is 1. Which means that if you divide an odd number by 2, you're going to need a real data type rather than an integer data type.

For example, 101 in binary (5 in decimal) divided by 10 (2) is 10.1 (2.5 in decimal). 101 divided by 100 (4) is 1.01, 101 divided by 1000 (8) is 0.101... you get the idea.

I don't know much about how computers represent non-integral numbers, but the point here is that if you divide an odd number number by a power of 2 (with a positive integer exponent), the result of that operation can't be held in an integer data type.


EDIT: For some strange reason I mistakenly thought the commenter was someone other than the asker, so I felt no urgency to respond. I only aimed to provide a different angle to look at this from, not give a rigorous proof.

But that's still easily done while looking at the bits of an integer data type. If $n$ is an odd number greater than 1, and $m$ and $\alpha$ are both positive integers, which may be even or odd, we seek to find $mn = 2^\alpha$. Let's say $n = 2k + 1$, where $k$ is a positive integer.

If $m$ is also odd, let's express it as $2j + 1$, with $j$ is also a positive integer. Then $mn = 4kj + 2k + 2j + 1$, an odd number. So $m$ must be even after all, so $m = 2j$. Then $mn = 4kj + 2j$, an even number, which is what we want. But $mn$ has at least two on bits, since $4 > 2$ and $kj > j$, but $2^\alpha$ has only one on bit, followed by $\alpha$ off bits.


Yes, that is correct, since the only prime factor(s) of any number $m = 2^b$ is $2$, while any odd number $n$ does not have $2$ as a prime factor. Hence, such $m$ and $n$ share no prime factors, and are therefore co-prime.