3
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ Hint Two positive integers are coprime iff they have no common prime factors (equivalently, iff their g.c.f. is $1$). What are the prime factors of $256$? $\endgroup$ – Travis Jan 15 '16 at 5:34
  • 1
    $\begingroup$ You seem to be combining a couple of questions, about numbers that are relatively prime to 256 (or co-prime), and numbers "in the range 1 to 256" which are not co-prime (to 256?). Are you also asking which of these "would be an easier question?" $\endgroup$ – hardmath Jan 15 '16 at 5:49
11
$\begingroup$

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$.

$\endgroup$
  • 2
    $\begingroup$ There are also quite a few odd numbers greater than 256... $\endgroup$ – hardmath Jan 15 '16 at 5:45
  • 6
    $\begingroup$ @hardmath Psshaw, name one! I mean, besides 87623 and 98723463. ...Okay, so there are at least a couple. $\endgroup$ – Chris Culter Jan 15 '16 at 6:01
  • 3
    $\begingroup$ I myself have been accused of being very odd! $\endgroup$ – hardmath Jan 15 '16 at 6:05
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @ mvw TY... I knew all the odd numbers would co-prime to 256, I didn't know if any others were... now I think about it, of course it's just the odds... all even numbers. Can you double confirm that's what you're saying? $\endgroup$ – Iam Nick Jan 15 '16 at 5:47
  • $\begingroup$ All even numbers have (at least) a 2 as a common factor. So no two even numbers are coprime to each other. An even number such as 14 is not coprime with any even number. But don't think that means it is coprime with every odd! 14 and 21 have 7 in common. But 256 is different. 256 has nothing but 2 as prime factors so it is coprime to every number that doesn't have 2 as a factor (odds) and not coprime to every number that does (evens). $\endgroup$ – fleablood Jan 15 '16 at 7:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.