Number theory: two relatively prime numbers, necessarily one must be odd and the other even?

Question

Let s and t be two different positive integers which are relatively prime. Does this property alone (of being relatively prime) NECESSARILY IMPLIES that one of s and t MUST be even and the other odd?

If yes, how would you prove so?

Answer 1

No, for example $3$ and $5$ are relatively prime, with both being odd integers. For that matter, all primes, including $2$, are relatively prime to each other.

Answer 2

If you know that one of the numbers is even, yes. All even numbers share a common factor of $2$ so can't be relatively prime.

However, if not then no. Use the representations of odd numbers as $En+O$ (where $E$ = even numbers, $O$ = odd) to see why. For example, all odd numbers are of the form $4n-1$ or $4n+1$. Can you show how any of the following pairs: $$4m-1, 4n-1$$ $$4m-1, 4n+1$$ $$4m+1, 4n+1$$ may or may not be relatively prime?

Answer 3

Suppose $a = \prod p_i^{k_i}$ is the unique prime factorization of $a$ and $b= \prod q_j^{m_j}$ is the unique prime factorization of $b$.

$a$ and $b$ being relatively prime means that none of $p_i$ equal any of the $q_j$ and vice versa.

$a$ is odd if none of the $p_i$ equal to $2$ and $a$ is even if one of the $p_i$ is equal to $2$. Likewise $b$ is odd if none of the $q_i$ are equal to $2$ and $b$ is odd if one of the $q_i = 2$.

So your statement is a matter of proving: If $\{p_i\}$ and $\{q_i\}$ are collections of primes with no primes in common, if one of the collections does not contain $2$, does that mean the other collection must contain $2$.

And the answer to that is: Of course not.

And to come up with a counter example we can have something as simple as $\{3\}$ and $\{5\}$ and $a = 3$ and $b = 5$. They are relatively prime and neither are even.

Answer 4

Counterexample with composite nunbers: pick several odd prime numbers (i.e. ones other than $2$), and multiply them together to get $a$. Pick several more that you didn't use the first time, and multiply those together to get $b$. $a$ and $b$ are both odd, and have no factors in common.

Two numbers being even means they're both divisible by $2$, but being odd only tells us that $2$ isn't a factor of either of them.