# Are these proofs correct? (Number Theory)

I'm finishing Chapter 1 of Apostol's book Introduction to Analytic Number Theory. I have made almost half of the 30 problems posed. I have some doubts on the proofs I produce, since sometimes I seem to assume extra information, or seem assume things that are obvious, when that is precisely what is to be proven. I am unsure about this few, however $(3)$ and $(4)$ seem right.

$(1)$

THEOREM If $(a,b)=1$ and $ab=c^n$, then $a=x^n$ and $b=y^n$ for some $x,y$.

PROOF If $(a,b)=1$ then we have

$$a = \prod p_i^{a_i}$$

$$b = \prod p_j^{b_j}$$

where $p_j \neq p_i$ for any $i,j$. Let $c=\prod p_m ^{c_m}$, and the $p_j$ and $p_i$ are uniquely determined. Then

$$ab=\prod p_i^{a_i}p_j^{b_j}=\prod p_m ^{nc_m}$$

But this means, since $p_i \neq p_j$, that

$$a_i =nc_{m_i}$$ $$b_j =nc_{m_j}$$

Thus

$$a = \prod p_i^{nc_{m_i}}=x^n$$

$$b = \prod p_j^{nc_{m_j}}=y^n$$

What I seem to be saying is "if $a$ and $b$ have no common prime factors and $ab=c^n$, then $a$ and $b$'s prime factors must be of multiplicity $n$. Else, $c$ wouldn't be a perfect $n$th power."

Apostol suggests considering $d=(a,c)$.

$(2)$

THEOREM For every $n \geq 1$ there exist uniquely determined $a<0$, $b>0$ such that $n=a^2b$, where $b$ is squarefree.

PROOF From the fundamental theorem of arithmetic, one has

$$n=\prod p_i^{a_i}$$ where the $p_i$ are unique. Group the product into two factors, according to the parity if the $a_i$s. If $a_i=2m_i$, write

$$n=\left(\prod p_i^{m_i} \right)^2 \prod p_l^{a_l}$$

The remaining $a_l$ are all odd, viz $a_i=2n_i+1$. Then write

$$n=\left(\prod p_i^{m_i} \prod p_l^{n_l}\right)^2 \prod p_l$$

$$n=a^2 b$$

Since the $p_i$ were unique, so are $a^2$ and $b$, and $b$ is clearly squarefree.

$(3)$

THEOREM If $2^n-1=p$, where $p$ is prime, then $n$ is prime.

Suppose $2^n-1$ is prime, and write $n=qp$. Then

$$2^n-1=2^{qp}-1=(2^q-1)(1+2^q+2^{2q}+\cdots+2^{q(p-1)}$$

thus $2^{q}-1\mid 2^n-1$, $\Rightarrow \Leftarrow$

$(4)$

THEOREM If $2^n+1$ is prime, then $n$ is a power of two.

Suppose that $2^n+1=p$, $p$ a prime, and $n$ is composite

$$n=ed$$ where $e$ is odd. Then it is clear $n \neq 2^m$ and $$2^n+1=2^{ed}+1=(2^d+1)(1-2^d+-\cdots+2^{d(e-1)})$$

Thus $2^d+1 \mid 2^n+1$. $\Rightarrow \Leftarrow$

Then $n$ can't have any odd factors, that is $n=2^m$ for some $m$.

NOTE: I mostly care about the proofs being correct or not. If they aren't let me know what the flaw is, and please hint a correction. I'm not looking for alternative proofs unless the proof is absolutely hokum.

-
 I am also working on Apostol as well. I have a question about Problem 1.14 where you have used the prime decomposition to prove what you want. I was wondering if it could be done just from the definition of gcd i.e. $(a,b) = 1 \implies ax+by = 1$. I tried to do it through this but I could not proceed much. For the second one, i.e. writing $n=a^2b$ you actually do not need to make use of the prime decomposition. You can in fact proceed directly by looking at the maximal square dividing $n$ and arguing based on that. For the third one, you need to write $n=qp$ and not $n=1p$. – user17762 Jun 11 '12 at 19:00 I am on chat now. – user17762 Jun 11 '12 at 19:01 I think all is right, but some typos! – H. Kabayakawa Jun 11 '12 at 19:31 @H.Kabayakawa Where? – Peter Tamaroff Jun 11 '12 at 19:32 In theorem about Mersenne primes you put $n=1p$. – H. Kabayakawa Jun 11 '12 at 19:38

Your proof is correct of 1 is correct; it is indeed saying that if a product of two relatively prime (positive) integers is a perfect $n$th power, then each is a pefect $n$th power. This is a generalization of a result of Euclid's which states that if $ab$ is a perfect square, and $a$ and $b$ are relatively prime, then each of $a$ and $b$ is a perfect square; this result is used to characterize Pythagorean triples in the Elements.
I'll assume that $n\gt 1$. To follow Apostol's hint, let $d=\gcd(a,c)$; then $d^n|c^n = ab$, and since $\gcd(d,b)|\gcd(a,b) = 1$, then $d^n|a$. Since $\gcd(a/d, c/d) = 1$, if we write $a=d^ny$ and $c=dx$, then $\gcd(d^{n-1}y,x) = 1$. But since $y|x^n$, it follows that $y=1$, so $a=d^n$.
Now use a symmetric argument to show to show $b$ is an $n$th power. Note that (I think) we did not use unique factorization into irreducibles, so this argument should work in any gcd-domain, not just in UFDs.
Your proof for 2 is almost okay, but you should really specify that $n=pq$ with $1\lt p,q\lt n$ if you want to argue by contradiction. Then your contradiction arises from the fact that you cannot have $2^q-1 = 1$ nor $1+2^q + \cdots + 2^{q(p-1)}=1$ (you never took this into account!). Alternatively, you can do it directly, by noting that if $n=pq$, then the factorization you give forces either $2^{q}-1=1$, or $1+2^q + \cdots 2^{q(p-1)}=1$, hence $p-1=0$.
Your argument for $3$ is not quite right, because we should not assume that $n$ is composite. If you want to argue by contradiction, you should only assume that $n$ is divisible by an odd number greater than $1$. And you also need to account for the possibility that the second factor in your factorization equals $1$; that is, that $$1-2^d + 2^{2d} -2^{3d}+ \cdots +2^{(2k)d} = 1.$$ The argument is that since $2^{2r} - 2^{2r-1}$ is positive, this can only happen if $2k=0$, hence the odd factor $e = 2k+1$ must be equal to $1$.