Divisibility problem cant use module just induction

In summary, the conversation discusses using induction to prove that 5 divides 8^n - 3^n, with a Natural Number n. The group suggests using the fact that 8 = 5 + 3 and showing that 5 divides Y-X if 5 divides X. They also provide step-by-step hints and a solution for William to use in his proof.
  • #1
Willy_Will
15
0
Hi all,

Great forum, I have been reading some cool stuff here for about a month.

Heres my question:
Using induction prove that 5 divides 8^n - 3^n, n Natural Number.

I know its true for n = 1, but I get stuck on the n = k+1. I don't know how to proceed from here: 8(8^k) - 3(3^k)

Also, I KNOW this is very easy using mod 5 but I can't do it here, I HAVE to prove it using only induction.

Any hints?

Thanks,

-William
 
Physics news on Phys.org
  • #2
If 5 divides X and you show that 5 divides Y-X, does 5 divide Y?
 
  • #3
I think so, but how can I use that in my problem?
 
  • #4
The fact that 8= 5+ 3 is very useful here!
 
  • #5
I think I've got it.

Suppose that 5 divides 8^k - 3^k ---> 8^k - 3^k = 5x, for some integer x.

case n = k +1
= 8^k+1 - 3^k+1
= 8(8^k) - 3(3^k)
= 8(8^k) - (3^k)(8) + (3^k)(8) - (3)(3^k)
= 8(8^k - 3^k) + 3^k(8 - 3)
(1) (2)

(1) by hypotesis 5 divides the expresion.
(2) 5 = 8 - 3, 5 divides 5.

= 8(5x) + 3^k(5)
= 5(8x + 3^k)

5 divides the expresion

Please tell me its that way, if not, point the errors and some hints.

Thanks, really.

-William
 
Last edited:
  • #6
I think I've got it.

Suppose that 5 divides 8^k - 3^k ---> 8^k - 3^k = 5x, for some integer x.

case n = k +1
= 8^k+1 - 3^k+1
= 8(8^k) - 3(3^k)
= 8(8^k) - (3^k)(8) + (3^k)(8) - (3)(3^k)
= 8(8^k - 3^k) + 3^k(8 - 3)
(1) (2)

(1) by hypotesis 5 divides the expresion.
(2) 5 = 8 - 3, 5 divides 5.

= 8(5x) + 3^k(5)
= 5(8x + 3^k)

5 divides the expresion

Please tell me its that way, if not, point the errors and some hints.

Thanks, really.

-William
 
  • #7
sorry for the double post.

(1) = (8^k - 3^k)
(2) = (8 - 3)

(1) by hypotesis 5 divides the expresion.
(2) 5 = 8 - 3, 5 divides 5.

= 8(5x) + 3^k(5)
= 5(8x + 3^k)

5 divides the expresion
 
  • #8
By George, I think he's got it!
 
  • #9
Thanks guys, I really appreciate it!
 

1. What is a divisibility problem?

A divisibility problem is a mathematical question that asks whether one number can be divided by another number without any remainder. For example, the question "Is 12 divisible by 3?" is a divisibility problem, and the answer is yes because 12 can be divided by 3 without any remainder.

2. How is the modulus operator usually used to solve divisibility problems?

The modulus operator, denoted by the symbol "%", is used to find the remainder when one number is divided by another number. In a divisibility problem, if the remainder is 0, then the numbers are divisible. For example, if we use the modulus operator to solve the problem "Is 12 divisible by 3?", the answer would be 12 % 3 = 0, which means 12 is divisible by 3.

3. Why can't the modulus operator be used to solve divisibility problems in this case?

The modulus operator cannot be used in this case because the question specifically states that we cannot use it. This may be to challenge the problem solver to think of alternative methods and to practice using other mathematical concepts, such as induction.

4. What is induction and how is it used to solve divisibility problems?

Induction is a mathematical proof technique that is used to prove statements about a sequence of numbers or objects. In the context of divisibility problems, induction can be used to show that a statement is true for all numbers in a certain range. For example, to prove that all even numbers are divisible by 2, we can use induction to show that the statement holds for the first even number (2), and then show that if it holds for any even number, it also holds for the next even number.

5. Can you provide an example of solving a divisibility problem using induction?

Sure, let's take the problem "Prove that all numbers of the form 2^n - 1 are divisible by 3, where n is a positive integer." Using induction, we can first show that the statement is true for the first number in this form, which is 2^1 - 1 = 1, and indeed 1 is divisible by 3. Then, we can assume that the statement is true for any number in this form, and show that if it holds for that number, it also holds for the next number. For example, if we assume that 2^k - 1 is divisible by 3, then we can show that 2^(k+1) - 1 is also divisible by 3, since 2^(k+1) - 1 = (2^k - 1) * 2 + 1, and 2^k - 1 and 2 are both divisible by 3, so their product is also divisible by 3. Therefore, by induction, we can conclude that the statement is true for all numbers of the form 2^n - 1 where n is a positive integer.

Similar threads

A Coefficients of Chebyshev polynomials
    • Linear and Abstract Algebra
Replies
2
Views
978
MHB Proving General Associativity for Group by induction
    • Linear and Abstract Algebra
Replies
5
Views
2K
MHB Show by induction that the determinant is equal to n
    • Linear and Abstract Algebra
Replies
10
Views
2K
A Finding the injective hull
    • Linear and Abstract Algebra
Replies
5
Views
1K
MHB Induction to find the determinant
    • Linear and Abstract Algebra
Replies
2
Views
3K
MHB Noetherian Modules, Submodules and Factor Modules .... Problem/Exercise
    • Linear and Abstract Algebra
Replies
21
Views
2K
Simple Induction Induction proof of Polynomial Division Theorem
    • Math Proof Training and Practice
Replies
10
Views
1K
I Is there any way to simplify my proof by induction?
    • General Math
Replies
13
Views
1K
MHB Show that these elements are linearly independent
    • Linear and Abstract Algebra
Replies
12
Views
1K
Induction with binomial coefficient
    • Calculus and Beyond Homework Help
Replies
15
Views
1K

Hot Threads

Recent Insights

Back
Top