Number Theory divisibility proof

In summary, the conversation discusses a homework problem where it needs to be proven that for any positive integer n, the integer (n(n+1)(n+2) + 21) is divisible by 3. The solution involves using a previously proved lemma, which states that if a number d divides both a and b, then it also divides their sum. By expanding the given expression, it can be seen that it is the product of three consecutive integers, and thus divisible by 3.
  • #1
jersiq1
7
0

Homework Statement


Prove that for any n [tex]\in[/tex] Z+, the integer (n(n+1)(n+2) + 21) is divisible by 3


Homework Equations



A previously proved lemma (see below)

The Attempt at a Solution



I sort of just need a nudge here. I have a previously proven lemma which states:

If d|a and d|b, then d|(a+b)

So armed with this I see that obviously 3|21 and all that remains is to prove n(n+1)(n+2) is divisible by 3. I have tried expanding, which didn't seem to help.
 
Physics news on Phys.org
  • #2
n(n+1)(n+2) is the product of __ consecutive integers.
 
  • #3
Wow! staring me in the face. Thanks.
 
  • #4
Cheers :)
 

1. How do you prove that a number is divisible by another number?

To prove that a number is divisible by another number, you need to show that the remainder is 0 when the first number is divided by the second number. This can be done by using various techniques such as prime factorization, modular arithmetic, or mathematical induction.

2. What is the difference between a direct proof and an indirect proof in number theory?

A direct proof involves using logical steps to show that a statement is true, while an indirect proof, also known as a proof by contradiction, involves assuming the opposite of the statement and showing that it leads to a contradiction. In number theory, both methods can be used to prove divisibility.

3. Can you give an example of a divisibility proof using mathematical induction?

Yes, for example, to prove that 11 divides 11n - 1 for all positive integers n, we can use mathematical induction. The base case, n=1, is true since 111 - 1 = 10, which is divisible by 11. Then, assuming that 11 divides 11k - 1, we can show that 11 divides 11k+1 - 1 by substituting k+1 into the equation and simplifying.

4. Are there any shortcuts or tricks for proving divisibility?

Yes, there are some common divisibility rules that can be used to quickly determine if a number is divisible by another number without performing the actual division. For example, a number is divisible by 2 if its last digit is even, and a number is divisible by 3 if the sum of its digits is divisible by 3.

5. How is divisibility related to prime numbers and factorization?

Divisibility is closely related to prime numbers and factorization because every integer can be expressed as a unique product of prime numbers. This means that to prove divisibility, we can use the prime factorization of the numbers involved. Additionally, prime numbers are only divisible by 1 and themselves, which is an important property in number theory.

Similar threads

  • Calculus and Beyond Homework Help
Replies
22
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
230
  • Calculus and Beyond Homework Help
Replies
3
Views
797
  • Calculus and Beyond Homework Help
Replies
1
Views
490
  • Calculus and Beyond Homework Help
Replies
1
Views
559
  • Calculus and Beyond Homework Help
Replies
1
Views
493
  • Calculus and Beyond Homework Help
Replies
7
Views
393
  • Calculus and Beyond Homework Help
Replies
3
Views
499
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
718
Back
Top