What numbers are relatively-prime to $256?$

Question

Given the numbers are in the range $1$ to $256$, which ones AREN'T co-prime, would be an easier question$?$

This question may be very specific and hopefully trivial for somebody on the maths board, but I ask ii because it's potentially relevant to the interest of cryptographers and yet somehow doesn't belong here.

Please don't flame me for asking such an easy question or one that may appear not to be relevant to other's interests... it will be relevant to the interest of people on the crypt o board but at the same time, isn't really a question apt for the crypt o site either.

Explaining the definition of "relatively prime" to $256$, without just linking to here, would be awesome!

Answer 1

A number is relatively prime to $256$ if it does not share any prime factors with $256$. Since $256=2^8$ has only one prime factor, namely $2$, this means a number is relatively prime to $256$ if it is not a multiple of $2$. In other words, if it is odd.

There are $128$ odd numbers between $1$ and $256$: $1,3,5,\ldots,251,253,255$.

Answer 2

An integer number $n$ is coprime to $256$ if the only divisors they have in common is $\pm 1$.

$256 = 2^8$ has the $18$ divisors $\pm 2^k$ with $k \in \{0, \dotsc, 8 \}$, thus $$ \{ -256, -128, -64, -32, -16, -8, -4, -2, -1, 1, 2, 4, 8, 16, 32, 64, 128, 256 \} $$

Which means all the even numbers are not coprime, because $2$ would be a common divisor. This leaves the odd numbers as coprime, because every integer number is either odd or even and odd numbers can not be divided by $2$.

Checking for the other divisors of $256$ is not necessary, because a number divisible by $\pm 2^k$, where $k > 1$, is also divisible by $2$.

Given the numbers are in the range 1 to 256, which ones AREN'T co-prime, would be an easier question?

The even numbers in the range of $1$ to $256$ are not coprime.