Least prime number....

Question

What is the least prime number which is a divisor of 7^9 + 11^25?

Answer 1

Hello Brian!

I hope I can help you answer this question. I have several different ways of approaching this problem, and I hope at least one of them will be helpful for you.

First, what are the prime numbers?

We have 2, 3, 5, 7, 11, 13 ...

And we want the least prime number that divides the sum 7⁹ + 11²⁵.

It seems reasonable to wonder if this number is divisible by 2 or not, since this is the least prime in general.

There are a couple different ways of figuring this out.

The first comes from number theory.

1.) An odd number plus another odd number is even.

For example, 3 + 5 = 8. 7 + 3 = 10, etc.

This works because all odd numbers can be written in the form

2k + 1 for some integer k.

(odd numbers are by definition not even, and all numbers are either even or odd, so all odd numbers must be 1 away from some even number)

So if we have 2 odd numbers we can write them as:

2k + 1, and 2l + 1.

Adding these together yields 2k + 2l + 1 +1

2k + 2l + 2

pulling out the 2 gives us:

2(k + l + 1).

This is a multiple of 2, and is therefore even.

2.) An odd number times another odd number is odd.

For example, 3*5 = 15.

7*11 = 77.

Using our definition of odd number from before, we can write two different odd numbers as:

2k + 1, 2l +1

multiplying these two numbers together yields:

(2k + 1) * (2l + 1)

= 2k*2l + 2k + 2l + 1

Factoring out 2 yields:

2(2kl + k + l) + 1

2kl +k + l is just some number, lets call it n

Then we have

2n +1, which is the same format as an odd number.

Thus this multiplication results in another odd number.

So, what does this mean?

Well, we have 7⁹ + 11²⁵, right?

which is 7*7*7*7... + 11*11*11...

An odd number times an odd number is odd, so both terms result in an odd number.

So we get some odd number, plus another odd number.

And as we noted before, the sum of two odd numbers is even.

So, we can conclude that 7⁹ + 11²⁵ is divisible by 2.

Since 2 is the smallest possible prime this is thus the smallest prime number which divides the sum.

Alternatively, we could use modular arithmetic.

If you are not familiar with these concepts, do not worry. I am including them here just for completeness.

Modular arithmetic simply refers to the remainder you get when dividing.

7 / 2 = 3 and 1 left over.

3/2 = 1 with 1 piece left over that 2 did not divide evenly into.

These remainders are what we are trying to find when doing modular arithmetic.

So when you see an expression like:

What is 7 mod 2?

What it really is asking is, when you divide 7 by 2 what is the remainder?

One way to determine this is to continually subtract 2 from 7 until we can do so no longer.

7 -2 = 5

5 - 2 = 3

3 - 2 = 1

So the remainder is 1, since we can do no more subtractions.

This is the same thing we get when we divide though.

7 / 2 = 3 + 1/2 (so 2 divides 7 three whole times)

7 - 2*3 = 1. There is 1 bit left over that 2 does not evenly divide into, and that is the remainder.

What if we wanted to know if 2 divided 7?

Well, if it evenly divided 7 then there would be no remainder, so we would have 7 mod 2 = 0.

Which is not true, since 7 mod 2 = 1, so 2 does not divide 7.

We can use this to find out if a sum is even or not, as we do below.

So, when we are working with exponents, we can use modular arithmetic to simplify things a bit.

If we have some arbitrary power of some number, like 7⁹, and we want to know if it is divisible by 2 we can pull out multiples of 2 from the base.

7⁹ (mod 2) = (7 (mod 2))⁹ = (1 (mod 2))⁹ = 1 (mod 2)

So, if we wanted to know if 7⁹ + 11²⁵ is divisible by 2 we could just check the remainder of the two terms.

7⁹ mod 2 is 1⁹, which is just 1.

11²⁵ mod 2 is likewise 1²⁵ which is 1.

1 + 1 (mod 2) = 0, so their sum is an even number.

If the sum was not divisible by two and you wanted to do the same kind of trick using 3, 5, 7, ....

You could use Fermat's Little Theorem.

I would be glad to explain how to use Fermat's Little theorem in the more complicated scenarios, but it was and is not necessary for solving this question so I did not include it here.

I hope one of these two approaches helped you!

Please do not hesitate to reply here if you have any questions or don't understand something.