Prove that 121ⁿ - 25ⁿ + 1900ⁿ -(-4)ⁿ

for any n (I think natural) is divisible by 2000

Thank you in advance.

OK, well we just have to check it is divisible by 125 and by 16. Do you know modular arithmetic? If not write back. If so let f(n) = 121ⁿ - 25ⁿ + 1900ⁿ - (-4)ⁿ .

f(n) = 9ⁿ - 9ⁿ + 12ⁿ - (-4)ⁿ (mod 16)

as 112,16,1888 are multiples of 16. And clearly 12 = -4 (mod 16).

So f(n) = 0 (mod 16) so f(n) is a multiple of 16.

Now to mod 125:

f(n) = (-4)ⁿ - 25ⁿ + 25ⁿ - (-4)ⁿ (mod 125)

as 1900 = 25 (mod 125). So f(n) = 0 (mod 125).

f(n) is a multiple of 125 and 16, and as these are coprime f(n) is a multiple of 125x16 = 2000, for all natural n.

Umm, this is correct, but that you can simplify the way you have is not obvious. I'll just explain why you can.
So, for example, take 121ⁿ (mod 16) = (112+9)ⁿ (mod 16) = 16(k) + 9ⁿ (mod 16) = 9ⁿ (mod 16). Where k is a polynomial in n.
This can be applied similarly to all the question. In fact in general, when n is a natural number. (hx+k)ⁿ (mod x) = x(f(n)) + kⁿ (mod x) = kⁿ (mod x).

Yes, I was assuming familiarity with modular arithmetic and its rules. The rule that:

a^k = b^k (mod r)

if

a = b (mod r)

can be shown by induction, or by the binomial expansion as Susan has done. The inductive proof is probably easier to write out:

If a = b (mod r) then we can say b = a + cr for some integer c. Now we want to prove a^k = b^k (mod r). This is easy for k = 1, and if it holds for k - 1:

a^k-1 = b^k-1 (mod r)

Multiply both sides by a: (it is easy to see you are allowed to do this)

a^k = ab^k-1 = (b - cr) b^k-1 = b^k - crb^k-1 = b^k (mod r)

so the result follows by induction.

This is a question of BMO1 [British Mathematical Olympiad - The Editor] last year. Of course we can do it by modular arithmetics, but it can also be done using factorisation.

First, note that 2000=16x125, and (16, 125) = 1.

First, we check for divisiblity of 16, which can be done in the following way:

121ⁿ -25ⁿ =(121-25)(121^n-1 +25x121^n-2 +...+25^n-1 )

which is obviously divisible by 16, as 121-25=96=6x16, and

1900ⁿ -(-4)ⁿ =(1900+4)(1900^n-1 +(-4)x1900^n-2 +...+(-4)^n-1 )

which is also divisible by 16, as 1904=16x119, so the sum of the two is divisible by 16.

Next, check for divisibility by 125 using a different combination, i.e.

121ⁿ -(-4)ⁿ and 1900ⁿ -25ⁿ

Kerwin

Nice!

Of course another possible approach would be to show that such an expression will obey a fourth order recurrence relationship with integral coefficients so all you need to do is check that it is divisible by 2000 for n = 0,1,2,3 and we're done. Unfortunately that is a bit tricky to do without a calculator and if you don't know about modular arithmetic, so the above approaches are preferable to this.

In general how do you go about showing something is divisible by something else? Say something simple like 2²ⁿ is always divisible by 2. If n is a positive integer.

Hal

Kerwin

As far as I know the only known method is to 'do the division,' i.e. to check that b | a find some c such that a = bc. There are techniques which can be used to speed up the process. Nearly all algorithms use the lemma:

Let a = x + y and suppose b | x then b | a if and only if b | y.
[ b | a means "b divides a", or "there exists some integer n such that a = nb".]

We do this all the time in our heads. Say we want to check if 102332 divides by ten. We say well 102332 = 102330 + 2 so 10 does not divide 102332.
This is the basis of arithmetic in finite fields. (modulo arithmetic).

I found this on a Cam website.
How would you approach this type of question.
Show that 2⁴ⁿ⁺² + 3²ⁿ⁺¹ is a multiple of 7 for all positive integers n.

What line of thinking would you approach this? Without using very specialised maths like you mentioned, ie modular math. I tackled using simple logic, but though I got into logical arguments, I was humbled and not able to answer the question!

Thanks for any help.
Hal

You can apply the arguments from modular arithmetic without explicitly using its notation.

2⁴ⁿ⁺² +3²ⁿ⁺¹ = 4.16ⁿ + 3.9ⁿ = 4(2.7+2)ⁿ + 3(2+7)ⁿ

which is divided by 7 if and only if 4.2ⁿ + 3.2ⁿ = 7.2ⁿ is (use binomial expansion if you like).


Like Anon says above the key point in all of these questions is to recognise:

'Let a = x + y and suppose b | x then b | a if and only if b | y.'

This statement is what modular arithmetic boils down to in the end, since the statement is 'if and only if' you really can't do this type of question without resorting, in some sense, to modular aritmemtic.

Hey William, Thanks!

Let me get that cup of tea and sit down at the desk properly to digest everything and I shall get back to you.

Hal

Why did you decide to the final bit as you did. eg 4(2.7+2)ⁿ + 3(2+7)ⁿ . What line of thinking did you follow to see this? How did you decide to break down the 16 and 9? Because it should be div by 7?

Thanks
Hal

Can someone set me another question similar to this, so I can test myself.

Hal

My method could be summarised along the lines of:

Derive an expression from 24ⁿ⁺² +32ⁿ⁺¹ which is divisible by 7 if and only if 24ⁿ⁺² +32ⁿ⁺¹ is so divisible. Hopefully it will be easy to see if this expression is divisible by 7 so we will have an answer.

How do we do the simplification. Using just about the only tool we have:

'Let a = x + y and suppose b | x then b | a if and only if b | y.'

Why did I adopt this approach? I suppose I've familiarity with congruences and modular arithmetic. The trick of dividing 16 and 9 by 7 is really obvious once you've seen it, but not at all obvious if you haven't. So I suppose I took the approach I did because I'd seen an example of something analagous before. It'd be pretty hard if you hadn't - a bit like asking someone to find the formula for the roots of a quadratic equation when they don't know how to complete the square.

Here's a harder but similar example, I got from Alan Baker's 'A Concise Introduction to the Theory of Numbers'

This is quite a bit harder to do, but you can do it using the same technique as above.

I'll have a go.
I'll put what I got after I've attempted it.

Thanks William,
Hal

I thought about the problem long and hard.
First I thought about factorising it. Then about multiplying out against each other.

Can I do this:
2² m - 1 = (2² )^m - 1 = 4^m - 1 ....?
2² n + 1 = (2² )^m + 1 = 4ⁿ + 1 ....?

I still don't fully understand the lemma?

What do I do next? Am I on the right lines of thought? Or way off. Be brutal. Its ok ;)

Ah - I'm afraid the ^ operation is not associative. That is: a^(b^c) is not necessarily equal to (a^b)^c (have a look for a counter-example).

As a hint for the problem let x = 2^(2ⁿ ) and y = 2^m-n . Now can you see that:

2^(2ⁿ ) + 1 = x + 1 while:
2^(2^m ) - 1 = x^y - 1?

It is perfectly natural (and healthy) to make the mistake of thinking ^ is associative at least ten times before it registers that ^ is not associative (it probably took far more than that for me!)

I must admit that I couldn't get the answer for ages, so I had a little peek in my Number Theory book. If you want a hint, read this, otherwise look away now:

Hal -

OK Here's a small clue.

Michael's method is nice and clear.

This lemma we were discussing earlier says that if we have an integer which we can express as the sum say

x = y + z

then suppose that a | y and y = ab so that

x = ab + z

then a divides x if and only if a divides z since if z = ac:

x = a(b+c)

and if a doesn't divide z a can't divide x.

Here's a brute force approach to proving the problem which is not as nice as Michael's but is a similar method to the one used in problem higher up.

If we put m = n + k then:

$(-1{)}^{2^k}-1=0$ is divided by $2^{2^n}+1$ which is always so. .

I proved it in the same way as Michael, but I like your method William!

I think the main problem with these types of questions is that they are quite easy to see how to do when someone tells you, but are quite difficult to prove from scratch, unless you've seen a similar question before, and even then it's not easy.

Good morning William, Michal and Olof!
Looks like you guys were busy while I hit the sack last night.

Michael thanks for pointing out the associative errors. Are there in general any other situations where people at first make a similar mistakes? Is it through a counter-example that we show its not associative? How would you show that something IS associative?

William thanks for your thoughts on the problem.
Olof, also thank you for your working and help.

Indeed you can disprove a^(b^c) = (a^b)^c through counter-example. e.g. Set b = 1, and the statement now reads a^(1^c) = (a^1)^c, so a = a^c for all a,c which doesn't sound too likely...

In fact sometimes where you place the brackets can make quite an astronomical difference. Consider for instance:

(10^10)^10 and 10^(10^10)

The former case is just 10000000000 multiplied by itself 10 times, so it is just 10^100 or 1 with 100 zeros following it.

On the other hand 10^(10^10) = 10^10000000000 which has 10000000000 zeros in it as opposed to 100. A slight change in notation really can make a lot of difference!

Thanks Michael!

Hal

Remember when NASA programmed their craft in Km, then another team entered the distance in mile! Or something similar.

Hal,

You may want to try out this related problem:

Prove that if aⁿ -1 is a prime, then a=2 and n is prime.

I don't think any hint is necessary, but just in case... remember how to factorise these sort of expressions!

Kerwin

Kerwin,

How about if I do this:
Let 'g' and 'h' be two integers (positive ones!).
(a^g - 1)(a^g(h-1) + a^g(h-2) + .. ..+ a+{g} + 1)
Am probably completly way off. I have currently not formal training in this type of math at all. Can you help me out to break this problem down and understand it. Lets see, we know that if aⁿ -1 is prime then it can not have any number apart from 1 and itself that can factor it/ or divide it. You talked about factorising it.

Thanks
Hal

Do you know the formula for geometric series?

1 + a + a² + ... + a^n-1 = (aⁿ -1)/(a-1)?
(where the first term is 1 and the common ratio is a)

If so, we can re-arrange this to get:

aⁿ - 1 = (a - 1)(1 + a + ... + a^n-1 )

This should help. You have got the right idea in saying that if aⁿ - 1 is prime it can't have any factor but 1 and itself...

Thank you Michael - you people are truly great!
I know of the g.p series. I didn't think of relating it to the problem at hand.

Hal.

Michael in your statement aⁿ - 1 = (a - 1)(1 + a +....+ a^n-1 ), don't a whole lot of terms cancel on the rhs?

Can anyone recommend any simple books that explain to its reader this type of math theory, I guess this is included in number theory? A book with review questions as well as its egs.

Hal

I think the factorisation of aⁿ - 1 is just a well known, useful fact - not one that would be especially emphasised in a number theory book (you'd probably be expected to know it before starting). Anyway I don't really know of any books on Number Theory at all (the one I have read is called From Polynomials to Sums of Squares , and though it is very good it is perhaps a bit specialised).

In the statement:

aⁿ - 1 = (a - 1)(1 + a + ... + a^n-1 )

then if you expanded the terms on the RHS then indeed lots of cancellation would take place. But if you try this you'll just find yourself back at the LHS...

Notice that if a > 2 then a - 1 is an integer, at least 2. Also 1 + a + ... + a^n-1 is an integer. So we have written aⁿ - 1 as (a - 1)xinteger, therefore aⁿ - 1 is not prime which is a contradiction. Therefore our assumption that a > 2 is incorrect, so a = 2 (a = 0,1 don't work either and there is an implicit assumption that a is not negative).

This completes the first part of the question. Now see if you can use a similar idea to show that if 2ⁿ - 1 is prime then n is prime. (This would complete the question.)

Micheal, so your saying from what I understand, it it can be factorised like you did, then it cannot be prime and hence it is a contradiction. Right?

As long as a - 1 is bigger than 1, yes. (If a - 1 = 1 then we have only written it as 1 x integer which does not show it is composite. If a - 1 is bigger than 1 then we have written the expression as (a - 1) x integer where a - 1 is bigger than 1 and also smaller than aⁿ - 1 so this does prove that aⁿ - 1 is composite.) Hence a - 1 = 1, or a = 2 is the only possibility. But this doesn't mean aⁿ - 1 is prime if a = 2 - only that it might be prime.

How would you show that n(n+1)(2n + 1) is divisible by 6.

Can you show by induction?
Is it like this?

f(n) = n(n+1)(2n+1)

let n=k
f(k) = k(k+1)(2k+1)
F(k+1) = k+1(k+1+1)(2(k+1)+1)

What do you do next?

Well, f(k+1)-f(k)=6(k+1)² is the inductive step.

f(k+1) - f(k)
= (k+1)(k+1+1)(2(k+1)+1) - k(k+1)(2k+1)
= (k+1)(k+2)(2k+3) - k(k+1)(2k+1)
= (k+1)[(k+2)(2k+3)-k(2k+1)]
= (k+1)(6k+6)
= 6(k+1)² as you got.

Thanks for your help.

Also this can be done without using induction.

Clearly n(n+1) has 2 as a factor as one of n and n+1 do. To get the factor of 3:
n if of one of the forms 3k,3k+1,3k-1.
If n is of the form 3k then n has 3 as a factor
If n is of the form 3k-1 then n+1 has 3 as a factor.
If n is of the form 3k+1 then 2n+1=2(3k+1)+1=6k+3 which has 3 as a factor.
So the product of n and n+1 and 2n+1 must have 3 as a factor.

Just to add another way of looking at it.

Susan

Susan,

I see what you are trying to do. It is a neat way of looking at it.

However I got lost with your line of reasoning on line three 'n if of one of the forms 3k,3k+1,3k-1. '. Can you explain for me? I do not fully understand.

Can you see where I went wrong with one?

n³ - n is a multiple of 6 for all positive integral n.

Again using induction (are there any other ways of showing this to be true?.. I would be interested to know).

Let, f(n) = n³ - n
Let n=k, f(k) = k³ - k,
Let n=K+1, f(k+1) = (k+1)³ - (k+1)

f(k+1)-f(k) = [(k+1)³ - (k+1)] - [k³ - k]
I got this down to, f(k+1)-f(k) = 3k² + 3k ... does this show what we were asked for????

Well, I should have said where k is an integer. So all integers are of one of the forms given.

Yes it works. The last term simplifies to 3k(k+1) and you can again use the argument about two consecutive terms to show it is divisible by 2.

And yes, there is a nicer way again:
n³ -n = n(n² -1) = n(n-1)(n+1) = (n-1)n(n+1)
So three consecutive numbers, so at least one must have two as a factor and and one must have three as a factor, so the product has 6 as a factor.

I hope that helps

Susan

Thank you Susan ;)
I like your method better than my method!

Hello again,

I did the following question, but ran into problems.

For all integrals of n, 2ⁿ⁺² + 3^{2n +1} is exactly divisible by 7.

Again by induction! (do you know of another way!- i would like to see if possible)
f(k) = 2^k+2 + 3^{2k +1}
f(k+1) = 2^k+1+2 + 3^{2(k+1) +1}

so, f(k+1)-f(k)= 2^k+1+2 + 3^{2(k+1) +1}
- 2^k+2 + 3^{2k +1}
I got this to, 4(2^k ) + 24(3^2k ).... I think is almost completly wrong??

One way to prove that f(n) = 2^{n + 2} + 3^{2n + 1} = 4x2ⁿ + 3x9ⁿ is a multiple of 7 is to note that f(n) is a solution of the difference equation:

f(n+2) - (2 + 9)f(n+1) + (2 x 9)f(n) = 0

So f(n) = integer x f(n-1) + integer x f(n-2)

So if f(n) and f(n+1) are multiples of 7 then f(n+2) is also a multiple of 7. (As it is equal to the sum of two multiples of 7.) Then by the same reasoning f(n+1), f(n+2) are multiples of 7, therefore so is f(n+3). And as f(n+2) and f(n+3) are multiples of 7, so is f(n+4), etc. Therefore all we need to do is to check that f(0) and f(1) are multiples of 7 and we're done.

f(0) = 4 + 3 = 7
f(1) = 8 + 27 = 35

So we are done.

In general this method can always be used to decide whether:

g(n) = a₁ b₁ ⁿ + a₂ b₂ ⁿ + ... + a_r b_r ⁿ

(where a₁ ,...,a_n and b₁ ,...,b_n are integers)

is a multiple of some integer p. All you need to do is to check that g(0), g(1), ..., g(r - 1) are all multiples of p, and that shows that g(n) is a multiple of p for all n > = 0.

If you don't know about difference equations then write back and I'll see if I can explain...

This is indeed a correct expression as far as I can see. However there is another form of induction that I will just try out.
Assume 2ⁿ⁺² +3²ⁿ⁺¹ = 7k for some integer k.
So 2ⁿ⁺³ +3²ⁿ⁺³ = 2*7k+7*3²ⁿ⁺¹ so if f(n) is divisible by 7, f(n+1) is also divisible by 7.
I prefer this way of looking at induction for non-simple inductions.
I don't know of any simplier method than this one. There are certainly other methods.

Susan

And in this case another (more standard) way is to see that:

f(n+1) - 2f(n) = (4x2ⁿ⁺¹ + 3x9ⁿ⁺¹ ) - 2(4x2ⁿ + 3x9ⁿ ) = 3x9ⁿ⁺¹ - 6x9ⁿ = 9ⁿ (27 - 6) = 21x9ⁿ

Therefore if f(n) is a multiple of 7 then f(n+1) = 2f(n) + 21x9ⁿ is a multiple of 7, and also f(0) = 7, so by induction f(n) is a multiple of 7. NB the reason that we consider f(n+1) - 2f(n) rather than f(n+1) - f(n) is that in the later case the 2ⁿ term doesn't get cancelled. In the former case it does so we're left with a simpler expression only involving 9ⁿ .

Michael, I don't know of the 'difference equation'. Can you explain. Thanks.

Susan, I tried it using your method, it worked, thanks!

Was not sure if this was correct.

(a) If n is an odd positive integer, proove that 2² + 1 is divisiable by 3

(b) If n is an even positive integer, proove that 2ⁿ - 1 is divisible by 3

for part (a)
Induction again.
f(n) = 2ⁿ + 1

Let n=k, f(k) = 2^k + 1
Let n=k+1, f(k+1) = 2^k+1 + 1
so, f(k+1)-f(k) = 2^k+1 + 1 - (2^k + 1)
= 2+{k} - 3m - 1 , is this correct???

I also tried this,
f(k+1) = 2^k+1 + 1 = 2(2^k ) + 1 = 2(3m-1) - 1 {where 2^k = 3m - 1} right? wrong?

Umm, this doesn't work as you are dealing with odd numbers and this means induction needs to deal with the case k+2 not k+1, so that it couldn't be right.

for part a), Hmm... 2² +1=5, so is not divisible by 3.

I suppose you mean 2²ⁿ⁺¹ +1 and 2²ⁿ -1 is divisible by 3, all n in N . For part a), we have

2^2(n+1)+1 +1 = 4(2²ⁿ⁺¹ +1)-3 is the induction step.

For part b), 2²ⁿ -1 = (2ⁿ +1)(2ⁿ -1) is the induction step.

Obviously these questions are easier if you do it via mod 3.

Kerwin

Susan, so if you deal with odd numbers you use (k+2) for induction, however like in part (B) if you use even positive, can you use (k+1) like in the previous questions?

Thanks also to Kerwin.

The even and odd numbers have a gap of two between two consecutive numbers. So for both when to induct to try to solve the case k+2 knowing the case k. Or, as kerwin has, yu can represent the odd numbers by all the numbers of the from 2n+1 where n is integer and the even numbers by 2n where n is integer. For induction in this case the gap is then 1 as normal.
Does that make sense?

Yes, it now makes sense.
Thank you very much Susan ;)

what do you mean by mod 3 Kerwin?

We know that 2²ⁿ - 1 = (2ⁿ + 1)(2ⁿ - 1). One of 2ⁿ -1,2ⁿ ,2ⁿ +1 is a multiple of 3, and it is not 2ⁿ , so (2ⁿ + 1)(2ⁿ - 1) is a multiple of 3, and so is 2²ⁿ - 1.

2^{2n + 1} + 1 = 2(2²ⁿ ) + 1 = 2(3k + 1) + 1 = 6k + 3 = 3(2k + 1) so it is a multiple of 3.

where 3k = 2²ⁿ - 1.

As for difference equations, note that if:

f(n) = p aⁿ + q bⁿ

then:

f(n) - a f(n-1) = q bⁿ - aq b^n-1 = b^n-1 q(b - a)

So letting z(n) = f(n) - a f(n-1) we get z(n)/z(n-1) = b and:

f(n) - a f(n-1) = b f(n-1) - ab f(n-2)
f(n) - (a + b) f(n-1) + ab f(n-2) = 0

So if f(n-1) and f(n-2) are a multiple of some number r then so is f(n). Hence if f(0) and f(1) are multiples of r then so are f(2),f(3),f(4),... etc. So whenever you get a problem like:

Show f(n) = 2ⁿ⁺² + 3²ⁿ⁺¹ is a multiple of 7, all you have to do is check f(0) and f(1) are a multiple of 7 and by induction, you've solved the problem. This easily extends upwards, to p aⁿ + q bⁿ + r cⁿ + etc. So if you ever get one with 3 powers, just check f(0) f(1) and f(2). In the BMO question at the top it suffices to check f(0) f(1) f(2) and f(3) but this would be very tedious without calculator/modular arithmetic.

Another question you might enjoy (I've just made it up):

If m,n,p,q are natural numbers with m > n and p > q and m,n coprime then let:

r = HCF(p,q)
s = HCF(m^p + n^p ,m^q + n^q )

where HCF = highest common factor.

Show that m^2r - n^2r is a multiple of s.

It only requires knowledge of modular arithmetic, and isn't really that hard then...