# Proof about relatively prime integers.

1. Apr 22, 2013

### cragar

This is not homework. If n is a positive odd integer then
n and $n+2^k$ are relatively prime. k is a positive integer.
Lets assume for contradiction that n and $n+2^k$ have a common factor.
then it should divide their difference but their difference is $2^k$ and since n is odd it has no factors of 2 so this is a contradiction and they are relatively prime.

2. Apr 22, 2013

### chiro

Hey cragar.

I'm not sure exactly what your lecturer expects, but you might want to write down a prime decomposition for n and the other number and show it in detail.

The intuition behind your proof is right but I'm not sure if your lecturer will want more.