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.

Problem. Let $d=(a,b)$, $b=\beta d$ and $n>1$. If $\beta$ is odd number, prove that $(n^a+1,n^b-1)\le 2$.

Solution (from the book). Each common divisor of numbers $n^a+1$ and $n^b-1$ has to be divisor of their sum $n^a+n^b=n^b(n^{a-b}+1)$, that is, it has to be a common divisor of $n^b-1$ and $n^{a-b}+1$ (we assume $a>b$). Keeping up, we conclude that the common divisor of numbers $n^a+1$ and $n^b-1$ has to be a divisor of number $n^d+1$. Let $x=n^d$, such that $n^b-1=x^\beta-1$ and $\beta$ is odd. To divide $n^b-1$ with $n^d-1$ means to divide $x%\beta-1$ with $x+1$. Remainder of this division is $-2$, and this means that numbers $n^a+1$ and $n^b-1$ cannot have common divisor greater than 2. $\square$

I'm horrible at number theory, because it always seems to abstract for me, and solutions always seem kind of forced, as if first the solution was written, and then the problem.

So I've decided to start from the beginning of my Introduction to number theory book, and this problem was supposed to be an easy example of previously learned.

There is a bunch of things I don't understand in this proof, beginning with "it has to be a common divisor of $n^b-1$ and $n^{a-b}+1$". After that, I understand literally nothing. I wish someone could write a more detailed explanation, but less formal, so that it can include many words and explanations, and examples, too.

Also, are there any hints/directions you could give me that I could follow when encountering number theory problems. What am I supposed to see, what am I supposed to look for, how much "deep" do I have to go to prove something (sometimes, some things sound pretty obvious to me, yet they are explained pretty long, and some things, as stuff I mention I don't understand, are simply gone though without a brief of explanation.

I hope I'm not asking too much.

share|improve this question

2 Answers 2

up vote 1 down vote accepted

The proof you were given is unnecessarily convoluted. In particular, the first part is totally unnecessary! We give an alternate proof in great detail.

We use congruence notation, because it is convenient. In a remark at the end, we show how you can avoid congruence notation, if you really want to, which you shouldn't.

We want to show that any (positive) common divisor $m$ of $n^a+1$ and $n^b-1$ is $\le 2$. Let $a=\alpha d$ and $b=\beta d$.

Because $m$ divides $n^{\alpha d}+1$, we have $$n^{\alpha d}\equiv -1 \pmod{m}.$$ Take the $\beta$-th power of both sides. Because $\beta$ is odd, we conclude that $$n^{\alpha\beta d}=(n^{\alpha d})^\beta \equiv (-1)^\beta\equiv -1 \pmod m.\qquad\qquad(\ast)$$ Similarly, and more easily, because $m$ divides $n^{\beta d}-1$, we have $$n^{\beta d}\equiv 1 \pmod{m}.$$ Take the $\alpha$-th power of both sides. We conclude that $$n^{\alpha\beta d}=(n^{\beta d})^\alpha \equiv 1^\alpha\equiv 1 \pmod m.\qquad\qquad(\ast\ast)$$

Compare $(\ast)$ and $(\ast\ast)$. We have simultaneously $n^{\alpha\beta d}\equiv -1 \pmod m$ and $n^{\alpha\beta d}\equiv 1 \pmod m$. It follows that $-1\equiv 1\pmod m$, that is, $2\equiv 0 \pmod m$. So we conclude that $m$ divides $2$, which is what we wanted to show.

Note that if $n$ is even, then $n^a+1$ and $n^b-1$ are both odd, so in that case, since their $\gcd$ divides $2$, we conclude that the $\gcd$ is actually $1$. Similarly, if $n$ is odd, then $n^a+1$ and $n^b-1$ are both even, so since their $\gcd$ divides $2$, it must be $2$.

Remark: We show how to dispense with congruence notation. We first used it to show that since $n^{\alpha d}\equiv -1 \pmod m$, we can conclude that
$(n^{\alpha d})^n \equiv -1 \pmod m$.

Without the congruence notation, we will prove that if $\beta$ is odd, and if $m$ divides $n^{\alpha d}+1$, then $m$ divides $(n^{\alpha d}+1)^\beta+1$. To see that nothing much is involved, let $y=n^{\alpha d}$. We want to show that if $m$ divides $y+1$, then $m$ divides $y^\beta+1$. This is easy, for if $\beta$ is odd, then $$y^\beta+1=(y+1)(y^{\beta-1}-y^{\beta-2}+y^{\beta-3}-y^{\beta-4}+y^{\beta -5}+\cdots +1).$$

Showing the other thing that we needed, namely that if $m$ divides $n^{\beta d}-1$, then $m$ divides $(n^{\beta d})^\alpha-1$ is even easier, there is no alternation of plus signs and minus signs.

share|improve this answer

The second half of the proof is more clearly presented using congruence arithmetic. Namely, working mod $\:m := (n^a+1,n^b-1)$ we have $ n^b\equiv 1$, so from $n^d\equiv -1$ we deduce

$$ 1 \equiv\ n^b \equiv (n^d)^{\beta} \equiv (-1)^{\beta}\equiv -1\ \ {\text by}\ \ \beta\ {\text odd}$$

Therefore $1 \equiv -1\ \Rightarrow\ 2 \equiv 0,\:$ i.e. $\:m\ |\ 2,\:$ as desired.

I haven't checked the details of the first half of the proof, but it should proceed mimicing the Euclidean algorithm, the same way as this proof that $\:(n^a-1,n^b-1) \: =\: n^{(a,b)}-1$.

share|improve this answer

Your Answer

 
discard

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.