Proving Divisibility

[Sauron]

Prove the following for all [MATH]n[/MATH] belonging to natural numbers:

1. [MATH]3^{5n} - 1[/MATH] and [MATH]5^{5n} - 1[/MATH] are divisible by [MATH]11[/MATH]
2. [MATH]3^{30n} - 1[/MATH] and [MATH]5^{30n} - 1[/MATH] are divisible by [MATH]77[/MATH]
3. [MATH]3^{60n} - 1[/MATH] and [MATH]5^{60n} - 1[/MATH] are divisible by [MATH]1001[/MATH]

I've tried Fermat's theorem and breaking it down into difference of squares/cubes but can't seem to figure it out.

 

[Cubist]

It's worth checking your notes to see if there's an example question with solution. This might tell you how you are supposed to solve these questions. If there is no example, then you could use this hint...

In base 10, consider a natural number x that has a last digit of "1". For example x=21 or x=341. Then, what would be the last digit of x*x, x*x*x, x^n ?

For question 1, 3^(5n)=243^n. And what is mod(243, 11)? (this gives the last digit of 243 when shown in base 11)

 

[Dr.Peterson]

Prove the following for all [MATH]n[/MATH] belonging to natural numbers:

1. [MATH]3^{5n} - 1[/MATH] and [MATH]5^{5n} - 1[/MATH] are divisible by [MATH]11[/MATH]
2. [MATH]3^{30n} - 1[/MATH] and [MATH]5^{30n} - 1[/MATH] are divisible by [MATH]77[/MATH]
3. [MATH]3^{60n} - 1[/MATH] and [MATH]5^{60n} - 1[/MATH] are divisible by [MATH]1001[/MATH]

I've tried Fermat's theorem and breaking it down into difference of squares/cubes but can't seem to figure it out.

Please state the theorem you are using, and show what you tried. You may be closer than you realize, but we can't tell without seeing your work.

@Kailey Forbes, the same applies to you! We need to know what you have learned and what you have tried.

 

[Cubist]

FYI: In my post#2 I was trying to give hints about the following property of modulo arithmetic:-

- If x,b, and n are natural numbers and mod(x, b)=1 then this implies that mod(x^n, b)=1

Have you been taught this? If not, then you should not use it (without proving it). Like @Dr.Peterson suggests please post back with your attempt based on what you can have been taught or more detail about your recent lessons.

 

[Kailey Forbes]

Oh ok am going to do what you say ok

 

[Sauron]

It's worth checking your notes to see if there's an example question with solution. This might tell you how you are supposed to solve these questions. If there is no example, then you could use this hint...

Thank you! I don't have any reference material besides my notes (this is sort of an enrichment class). I've proven the results but am still somewhat unwieldy with them. Solved the first question using the method you suggested, but I'm struggling with the last two. This is my progress so far:

[MATH]3^{30n} -1 = (3^{15n} +1)(3^{15n} -1)[/MATH]Since [MATH]3^{5n}\equiv 1\pmod {11}[/MATH]then [MATH]3^{15n}\equiv 1\pmod {11}[/MATH] as well
So now all we have to prove is that [MATH]3^{15n} + 1[/MATH] is divisible by [MATH]77/11 = 7[/MATH]
I did the same thing for the last problem as well:
[MATH]3^{60n} -1 = (3^{30n} +1)(3^{30n} -1)[/MATH]Since we already proved [MATH]3^{30n} -1[/MATH] is divisible by [MATH]77[/MATH] in the previous question, the question is reduced to proving that [MATH]3^{30n} +1[/MATH] is divisible by [MATH]1001/77 = 13[/MATH].

I'm at a loss on how to proceed past this step in both questions. For reference, my knowledge extends upto Fermat and Wilson's theorems

Edit: I realize you can just expand [MATH]3^{15}[/MATH] and [MATH]3^{30}[/MATH] respectively and solve it as we solved the first one (though [MATH]3^{5}[/MATH] is a much more benign calculation), but was wondering if there was any other way to do it without a calculator.

 

[JeffM]

I would probably do a brute force attack on statement 1 using induction.

Let’s take as an example of brute force the proof of this theorem.

[MATH]n \text { is a positive integer } \implies 7 \ | \ 2^{3n} - 1.[/MATH]
[MATH]n = 1 \implies 2^{3n} - 1 = 2^3 - 1 = 8 - 1 = 7 \implies 7 \ | \ 2^{3n}.[/MATH]
[MATH]\text {So, there is at least one positive integer for which the proposition is true.}[/MATH]
[MATH]\text {Let } k \text { be an arbitrary one of those positive integers.}[/MATH]
[MATH]\therefore \exists \text { integer } m_k \text { such that } 7m_k = 2^{3k} - 1.[/MATH]
[MATH]2^{3(k+1)} - 1 = 2^{3k + 3} - 2^{3k} + 2^{3k} - 1 = 2^{3k}(2^3 - 1) + (2^{3k} - 1) =[/MATH]
[MATH]7 * 2^{3k} + 7m_k = 7(2^{3k} + m_k).[/MATH]
[MATH]\text {Let } m_{k+1} = 2^{3k} + m_ k.[/MATH]
[MATH]\therefore m_{k+1} \text { is an integer } \ \because \ m_k \text { is an integer.}[/MATH]
[MATH]\therefore \exists \text { integer } m_{k+1} \text { such that } 7m_{k+1} = 2^{3(k+1)} - 1.[/MATH]
And so the proposition is true for all positive integers.

I am sure that cubist is correct that an elegant proof is possible with modulo arithmetic, but you can give a proof based on nothing more than the definition of “is divisible by.”

 

[Harry_the_cat]

Q1 is easy enough by proof by induction. The size of the numbers in Q2 and Q3 make induction tricky - which suggests there must be another (better) way.

 

[JeffM]

This is a proof that does not require a calculator.

The proposition to be proved is:

[MATH](m, \ n, \ p, \ q\text { are positive integers}) \land (m > 1) \land (m \ | \ p^q - 1) \implies[/MATH]
[MATH]m \ | \ p^{nq} - 1.[/MATH]
Proof

[MATH]\text {By hypothesis, } m \ | \ p^q - 1 = p^{1 * q} - 1.[/MATH]
[MATH]\therefore \text {Proposition is true if } n = 1.[/MATH]
[MATH]\text {Furthermore, } \exists \text { integer } j_1 \text { such that } j_1 * m = p^q - 1.[/MATH]
[MATH]\therefore \text {There are one or more positive integers for which proposition is true,}[/MATH]
[MATH]\text {Let } k \text { be an arbitrary one of those positive integers.}[/MATH]
[MATH]\therefore k \text { is an integer} \ge 1 \land m \ | p^{kq} - 1.[/MATH]
[MATH]\therefore \text {By the definition of divisibility, }\\ \exists \ \text { an integer } j_k \text { such that } j_k * m = p^{kq} - 1.[/MATH][MATH]p^{(k+1)*q} - 1 = p^{(k+1)*q} - (p^{kq} - p^{kq}) - 1 \implies[/MATH]
[MATH]p^{(k+1)*q} - 1 = p^{kq}(p^q - 1) + (p^{kq} - 1) \implies[/MATH]
[MATH]p^{(k+1)*q} - 1 = p^{kq}(j_1 * m) + (j_k * m) = m * ( p^{kj} * j_1 + j_k).[/MATH]
[MATH]\text {But } p^{kj} * j_1 + j_k \text { is an integer.}[/MATH]
[MATH]\therefore \text {By the definition of divisibility, } m \ | \ p^{(k+1)q} - 1.[/MATH]
Once we have this general theorem, we can move along as follows.

[MATH]3^5 - 1 = 243 - 1 = 242 = 2 * 11^2 \implies 11 \ | \ 3^5 - 1.[/MATH]
[MATH]3^6 - 1 = 729 - 1 = 728 = 2^3 * 7 * 13 \implies (7 \ | \ 3^6 - 1) \land (13 \ | \ 3^6 - 1).[/MATH]
Then our theorem says that 7, 11, and 13 are all divisors of both 3^(30) - 1 and 3^{60} - 1, blah blah blah

If I knew more math I could probably give a more elegant proof, but I think this one is pretty solid.