Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.


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


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


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.


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

PROOF Reductio ad absurdum.

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


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


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

PROOF Reductio ad absurdum.

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.

share|improve this question
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? –  Pedro Tamaroff Jun 11 '12 at 19:32
In theorem about Mersenne primes you put $n=1p$. –  H. Kabayakawa Jun 11 '12 at 19:38

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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