Abstract Algebra Proof (factorization?)

[dancergirlie]

Homework Statement

If n is a nonzero integer, prove that n cam be written uniquely in the form n=(2^k)m, where k is greater than or equal to zero, and m is odd

Homework Equations

It is in the primes and unique factorization chapter so maybe that every integer n (except 0 and 1) can be written as a product of primes

The Attempt at a Solution

I am not sure, but I tried to do a proof by induction on n

Let n=1
so, 1=(2^k)(m)
1=(1)(1)=1 where k=0 and m=1
so the statement holds for n=1

Now assume the statement holds for n=(r-1) for any integer (except 0 and 1)
so
(r-1)=(2^k)(m) where k is greater than or equal to zero and m is odd

Now let n=r
so r=(2^k)(m)

This is where I don't know what to do... that is why I'm thinking there is an easier way to do this besides induction. Any help would be appreciated =)

 

[mighty2000]

Your attempt at using induction is a good start, but there is indeed a simpler way to prove this statement. Instead of using induction, we can use the Fundamental Theorem of Arithmetic, which states that every integer (except 0 and 1) can be written as a unique product of primes.

Let's start by considering an arbitrary nonzero integer n. By the Fundamental Theorem of Arithmetic, we know that n can be written as a product of primes, say p1, p2, p3, ..., pk. So, we can write:

n = p1 * p2 * p3 * ... * pk

Now, we can group the primes into two sets: the set of all even primes, and the set of all odd primes. Let's call these sets E and O, respectively. Since n is nonzero, it must contain at least one prime, so both E and O are non-empty sets.

Next, we can rearrange the terms in the product such that all the even primes are grouped together, and all the odd primes are grouped together. This can be done by simply factoring out all the powers of 2 from the product. So, we can write:

n = (2^a) * (p1' * p2' * p3' * ... * pk')

where p1', p2', p3', ..., pk' are all odd primes, and a is a non-negative integer.

Now, we have expressed n in the desired form, with k=a and m=p1' * p2' * p3' * ... * pk' (which is odd).

Lastly, we need to show that this expression is unique. Suppose there exists another expression for n in the form n=(2^b)m, where b is a non-negative integer and m is odd. Then, we have:

(2^a) * (p1' * p2' * p3' * ... * pk') = (2^b) * m

Since the two expressions are equal, we can cancel out the common factor of (2^b) on both sides to get:

p1' * p2' * p3' * ... * pk' = m

But this means that all the primes in the product on the left-hand side are odd, while m is also odd. This implies that both sides of the equation have the same set of primes, which contradicts