#1
|
|||
|
|||
Divisibility by 5
I'm trying to prove that for all integer values of n
9^n - 4^n is a multiple of 5 by induction. I have having trouble that p(n) implies p(n+1). If anyone knows how to do this, any help would be appreciated. |
#2
|
|||
|
|||
Re: Divisibility by 5
9^(n+1) = 9 * 9^n, 4^(n+1) = 4* 4^n,
9^(n+1) - 4^(n+1) = 9* 9^(n) - 9* 4^(n) + 5*4^(n)= 9 * ( some multiple of 5) + 5*(some integer) |
#3
|
|||
|
|||
Re: Divisibility by 5
This is simple 9^(n+1)-4^(n+1)=9*9^n-4*4^n=5*9^n+4*(9^n-4^n) which is trivially divisible by 5 if 9^n-4^n is.
|
#4
|
|||
|
|||
Re: Divisibility by 5
Let me try to clear this up a bit:
Let 9^n - 4^n = 5*i where i is some integer. 9^(n+1) - 4^(n+1) = 9*(9^n) - 4*(4^n) = 9*(9^n) - 9*(4^n) + 5*(4^n) = 9*(9^n -4^n) + 5* 4^n) = 9*(5*i) + 5*4^n = 5*(9*i + 4^n). QED. |
#5
|
|||
|
|||
Re: Divisibility by 5
Beat me by 3 minutes. I knew I shouldn't have looked over the reasoning that extra time.
|
#6
|
|||
|
|||
Re: Divisibility by 5
thank you
|
#7
|
|||
|
|||
Re: Divisibility by 5
No problem.
The crux of the proof is that 9=4+5. I believe that it is a trivial extension to further show that for any three natural numbers A,B,C such that A=B+C that C divides A^n - B^n for all n. I think this is totally obvious, but am too lazy to check carefully. This is probably well known, but I am too much of a mathematics novice to be aware of that or not. I did check a few cases and it always worked. |
#8
|
|||
|
|||
Re: Divisibility by 5
[ QUOTE ]
I believe that it is a trivial extension to further show that for any three natural numbers A,B,C such that A=B+C that C divides A^n - B^n for all n. [/ QUOTE ] It's simply because A = B mod C. No induction required. |
#9
|
|||
|
|||
Re: Divisibility by 5
9 = 5 mod 4? Try again.
|
#10
|
|||
|
|||
Re: Divisibility by 5
He means 9 = 4 mod 5.
Look: (5 + 4)^n - 4^n mod 5 is obviously equal to 4^n - 4^n mod 5, which is 0 mod 5. |
|
|