As an IB student in grade 11 who has half-yearly examinations for Mathematics tomorrow you really made me feel smarter about myself and give me that confidence, I really respect you! I'm happy that my teacher is also good, everyone should be blessed with a teacher like you sir.
I'm an engineer and I watch a lot of science and math related videos, but I don't think I've seen this sort of divisibility proof before. Thanks for making the video! It was well explained, and I learned something new!
Right, but induction is a way to prove that that first -> is valid: * 11^n = 4^n mod 7 is true for n=1 * For any n, if 11^n = 4^n, then (11^n)*11 = (4^n)*4 mod 11, i.e. 11^(n+1) = 4^(n+1)
@@emurphy42 No, because the product of 2 congruences is also a congruence (rule of multiplication of congruences)! 11 ≡ 4 mod(7) and 11 ≡ 4 mod(7) ---> 11*11 ≡ 4*4 mod(7) ...
@WahranRai Sure, but that only covers the jump from n=1 to n=2. Yes, intuitively it keeps going for all n, but that's what induction -is-, it's the formal equivalent of that intuition: * if it works for the first element of a sequence * and if it working for any one element of that sequence implies it also working for the next element * then it works for every element of that sequence
@@emurphy42 I told you it is not necessary to use induction. In modular algebra you have the same operation as with integers.. x=y ---> x^n = y^n It is known and you do not have to demonstrate it by induction...
@@WahranRaiit is a well established result, but... It is not an axiom of the mathematical system. How do you think this result was proven? More precisely, how does one go about proving this well known result without induction? I am not sure you can.
I shall give a quick method using theory of binomial (a+b)^n= a^n+nC1a^(n-1)b+.............+nCn b^n So we can write 11^n=(7+4)^n Now problem reduces to- (7+4)^n-4^n =>4^n+nC1(4^n-1)[7]+.......+7^n -4^n So we 4^n gets cancelled and thereby every term left containes a factor of 7. HP
Alternatively: aⁿ-bⁿ=(a-b)(aⁿ⁻¹ + aⁿ⁻²b¹ + aⁿ⁻³b² + .... +a¹bⁿ⁻²+bⁿ⁻¹) You can remember that as a notable product(just like you know (a+b)ⁿ is a binomial).... alternatively. let's take S=aⁿ⁻¹ + aⁿ⁻²b¹ + aⁿ⁻³b² + .... +a¹bⁿ⁻²+bⁿ⁻¹ This is a geometric progression with factor b/a and n terms.... using the geometric sum formula: S=aⁿ⁻¹ (1 - (b/a)ⁿ) / (1 - (b/a)) S=a(aⁿ⁻¹ - bⁿ/a) / (a - b) S=(aⁿ - bⁿ) / (a - b) Alternatively, using the geometric sum trick, take S and multiply by (b/a) (b/a)S = aⁿ⁻²b¹ + aⁿ⁻³b² + .... +a¹bⁿ⁻²+bⁿ⁻¹+bⁿ/a Subtract from S: S - (b/a)S = (aⁿ⁻¹ + aⁿ⁻²b¹ + aⁿ⁻³b² + .... +a¹bⁿ⁻²+bⁿ⁻¹)-(aⁿ⁻²b¹ + aⁿ⁻³b² + .... +a¹bⁿ⁻²+bⁿ⁻¹+bⁿ/a) Note how almost all terms in the RHS are the same, except aⁿ⁻¹ and bⁿ/a S - (b/a)S = aⁿ⁻¹-bⁿ/a (Lore: the induction is hidden on this step... this is a telescoping sum) (1-(b/a)) S = (1/a)(aⁿ-bⁿ) S = (1/a)(aⁿ-bⁿ) / (1-(b/a)) If you arrange it out you should arrive at the same expression back again. The geometric sum fails at a=0... in this case aⁿ-bⁿ=(a-b)(aⁿ⁻¹ + aⁿ⁻²b¹ + aⁿ⁻³b² + .... +a¹bⁿ⁻²+bⁿ⁻¹) Becomes: bⁿ=(-b)(bⁿ⁻¹) And there also a division by 0 induced when a=b... in this case aⁿ-bⁿ=(a-b)(aⁿ⁻¹ + aⁿ⁻²b¹ + aⁿ⁻³b² + .... +a¹bⁿ⁻²+bⁿ⁻¹) Becomes aⁿ-aⁿ=(a-a)(....) 0=0 Which also checks out(Bonus lore: you can use that to prove the derivative of xⁿ is nxⁿ⁻¹ if you are careful on this case)
I'm from morocco and I want to say that your so good as a math teacher . I undrstood the example you did and I use to apply the method in other exersises
a-b is always a factor of a^n - b^n, using factor theorem put a^n by x^n , then putting x= b in equation x^n- b^n =0 gives 0, thus by factor theorem x-b is factor of x^n - b^n
I did it like this: n = 1: 7 | 11-4 7 | 7 ✅ n => n+1: 7 | 11^n-4^n 7 | 11^(n+1)-11*4^n 7 | 11^(n+1)-4*4^n-7*4^n since a | b and a | c a | b+c 7 | 11^(n+1)-4^(n+1) ✅
I woched many videos from different tutors but finally Ive understood this one, Tomorrow I'm writing my final exam,MSM111 ,and I believe I'm going to make it🙌
Wonderful video and a much cleaner solution than I would have used. I consider the series 11^n-4^n from 1 to k+1. Like you I started with the first term of the series 11^1-4^n=7 which is divisible by 7. Then I followed the same logic as your video for the term of the series k+1 to get to 11^k+1-4^K+1=7(11^k)-4(11^k-4^k). I noted that 11^k-4^k is of course the preceding term in my series which could be expanded using the same logic so no matter what value k+1 is you end up that 11^k=1-4^k+1=7(11^k)-4(7(11^k-1)-4(7(11^k-2)-...4(7))))) and as every term in the right hand side of the equation is a multiple of 7 it follows that the right hand side is divisible by 7
We can also use Binomial to prove this. Let 11^n = (7 + 4)^n = 7^n+ ....+4^n. After the last term is subtracted, the remaining terms all have factor 7.
this one is straight out of an advanced calculus book haha! it is a problem in chapter one of Kenneth A. Ross: Analysis the Theory of Calculus -- love it!
Another method is to multiply P(k) by (11+7) P(k)*(11+7) = (11^k - 7^k)*(11+7) = (11+7)(11-7)m 11^(k+1) + 11^k.7 - 11.7^k - 7^(k+1) = (11-7)(11+7)m 11^(k+1) - 7^(k+1) = (11-7)(11+7)m + 11*7^k - 7*11^k P(k+1) = (11-7)(11+7)m + 11*7^k - 7*11^k The first term (11-7)(11+7)m is obviously divisible by 11-7 so we need to focus on 11*7^k - 7*11^k Since 7 and 11 are factors of both remaining terms we can rewrite 11*7^k - 7*11^k = 7 *11*[ 7^(k-1) - 11^(k-1) ] We notice that 7^(k-1) - 11^(k-1) is P(k-1) so the final formula is P(k+1) = (11-7)(11+7)m + 7*11*P(k-1) And of course, that method requires to manually verify the first TWO steps P(1) and P(2).
Binomial theorem also works. Split 11^n into (7+4)^n and use the theorem to split it up to a sum of (7^i * 4^(n-i)) with some other factorials and crap. When i=0, the 0th term becomes 4^n and every term after is a multiple of 7. 4^n is cancelled out by the original 4^n we had, so we're only left with a sum of terms that are all multiples of 7, which means they're always going to be divisible by 7.
a^n -b^n is always divisible by (a-b) if a,b,n are integers. Proof: Assume a^k - b^k be divisble by (a-b). That means, a^k - b^k = (a-b)m where m is an integer ....... Eqn. (1) Now a^(k+1) - b^(k+1) = a.a^k - b.b^k That is, a^(k+1) - b^(k+1) = (a-b+b)a^k - b.b^k That is, a^(k+1) - b^(k+1) = (a-b)a^k +b.a^k - b.b^k That is, a^(k+1) - b^(k+1) = (a-b)a^k+b(a^k - b^k) That is, a^(k+1) - b^(k+1) = (a-b)a^k +b(a-b)m substituting a^k - b^k with Eqn.(1) That is, a^(k+1) - b^(k+1) = (a-b)(a^k+b.m); Hence, a^(k+1) - b^(k+1) is divisible by (a-b) Therefore, by Mathematical induction a^n-b^n is divisible by (a-b) if a,b,n are integers.
take the first natural n=1: 11-4=7 , divisible by 7 suppose that when n=k, 11ˆk-4ˆk=7m then test to n=k+1 11^(k+1)-4^(k+1) 11.11^k-4.4^k (7+4).11^k-4.4^k 4(11^k-4^k)+7.11^k 4.7m+7.11^k is always divisible by 7 (k, m are integers)
We can do better. There's nothing special about 11 and 4 here. Claim: a^n - b^n is divisible by a - b for any positive integer n. Base case: n = 1. If n = 1, then a^n - b^n = a^1 - b^1 = a - b. And a - b is divisible by a - b. Inductive case: Assume it's true for n = k, so a^k - b^k = (a-b)m. Consider the case when n = k+1. a^(k+1) - b^(k+1) = a^k . a - b^k . b = (a - b + b) a^k - (b) b^k = (a - b) a^k + b . a^k - b . b^k = (a - b) a^k + b (a^k - b^k) = (a - b) a^k + b ((a - b) m) = (a - b) (a^k + bm). Since a^k and bm are both integers, we know that (a - b) (a^k + bm) is divisible by (a - b), so a^(k+1) - b^(k+1) is divisible by (a - b).
with the congruence principle, we can subsitute any number in any step with a value congruent mod 7. So we can write the thesis as the following expression 11^n - 4 ^n = 0 mod 7, because 11 = 4 mod 7 we obtain 4 = 4 mod 7 that is true.
BASE CASE: 0 11^0 - 4^0 = 0 = 7(0) P(k + 1), by mathematical induction, P(n) must be true for all n where n is contained within the set of natural numbers.
for even numbers, it's divisible by 7 (because 11²-4²=(7)(15) and 11⁴-4⁴=(121-16)(121+16)=(105)(137)=(7)(15)(137)) and for numbers that are divisible by 3, it's also divisible, but i don't know how with primes (sorry for bad english)
11^n is (7 + 4)^n. Every element in this polynomial, except for the last, is multiplied by 7 at least once, making it so only the last one (which is 4^n), isn't divisible by 7. This one cancels out with -4^n, making 11^n - 4^n divisible by 7.
For any positive integer n, aⁿ - bⁿ = (a - b)(aⁿ⁻¹b⁰ + aⁿ⁻²b¹ + aⁿ⁻³b² + aⁿ⁻⁴b³ + ... + aⁿ⁻ⁿbⁿ⁻¹). This factorization is valid for both odd and even n. More fun with math: For any *odd* positive integer n, aⁿ + bⁿ is divisible by a + b by the factorization aⁿ + bⁿ = (a + b)(aⁿ⁻¹b⁰ - aⁿ⁻²b¹ + aⁿ⁻³b² - aⁿ⁻⁴b³ + ... + aⁿ⁻ⁿbⁿ⁻¹). Not for even n, however.
Binomial expansion approach avoids having to be concerned about the parity of n. (B+km)^n = B^n+(n¦1) B^(n-1) km+(n¦2) B^(n-2) (km)^2+⋯+(km)^n congruent to B^n (mod m)
Induction is overkill for this problem. 11 ≡ 4 modulo 7, so (11^n - 4^n) ≡ (4^n - 4^n) ≡ 0 modulo 7 QED (11^n - 4^n) ≡ (4^n - 4^n) follows from the Binomial theorem which holds ∀ n ∈ N(This is why induction is unnecessary)
One man's overkill is another man's natural way to do it. The purpose of the video was probably to show how it can be done without knowing modular arithmetic nor additional theorems.
@@ingo-w modular arithmetic is a fancy phrase for basic integer divisibility properties. Integer divisibility is easier than induction which is not usually taught in high school. Many first learn about induction in a graduate level number theory course.
yep it is easy induction starts from n = 1 : 11 - 4 = 7 in 11^n - 4^n div 7, view 11*11^n - 4*4^n = 11*11^n -4*11^n + 4 * 11^n - 4*4^n (added and substracted 4*11^n )= 11^n (11-4) - 4(4^n - 11^n). if 4^n - 11^n div 7, then whole expression what is equal to 11*11^n - 4*4^n is div 7
You need to either prove that it is true for the kth instance of 11^k - 7^k, or show a proper relation between the 1st instance and the kth, then your proof is done (for positive integer instances). While you might say this is implicit from the 1st term, it isn't explained clearly in your proof. The point of a proof isn't just to have the correct assumption but also to show how/why it is true. Like others said, this can be proven with binomial expansion. Induction isn't needed.
Not necessarily. You can start the induction with any n you want, but of course you have to show also that it holds for numbers that are lower than n. Which is in this case particularly easy with n=0.
@@YoussefSaydi No. Suppose you didn't see that it holds for all natural numbers and thought that it holds only for natural numbers > 0. Then you would start the induction with 1, just like in the video. Then you obtain a valid proof that the proposition holds for all n > 0. Add to this the trivial observation that it holds for n = 0 also and you have the proof that it holds for all natural numbers. In the same way, you could start the induction with, say, n=3 and then proove it for n in 0,1,2 afterwards to reach a valid proof that it holds for all natural numbers. Though I wouldn't do it that way but start with n=0 like you suggest, but it's valid proofs nevertheless just a bit more complicated since you need the extra proofs for the lower ns.
Hello sir ❤, thanks for this video I have a doubt, 'm' will never be a -ve number and zero. Then why are you saying 'm' is an integer 😂. I will say 'm' is a natural number. If you say that both are correct then I will say 'm' is a Complex numbers( set of all kinds of numbers 😂😂😂😂😂). If you say a natural number then problem solved. Other wise it is a debatable topic 😂😂. anyway thank you sir for this video. My poor English hop you understand 😁
I see. It makes sense to to relate a^n-b^n=(a-b)(a^(n-1)+a^(n-2)b+...+b^(n-1)) I wanted to use binomial expansion by writing 11^n-4^n=(7+4)^n-4^n = choose(n,k)*7^(n-k)*4^k -4^k . So 4^n cancel out and we are left with all the terms for k from 0 to n-1 which all contain a multiple of 7. Qed My thought went to a problem I knew before: Show that fraction (2^(n+3) + 3^n*5^(n+1))/(2^(n+2)×3^(n+1)+5^(2n)) Is always reductible by 13
Unfortunately this came a little short in the video. It was shown for n=1. So the assumption is right for 1, therefore also right for 2. And when it's right for 2, then it's also right for 3 - and so on.
Sorry, but this is trivial. Since a^n - b^n = (a - b)( a^(n-1) + a^(n-2)b + a^(n-3)b^2 + ... +ab^(n-2) + b^(n-2) ), it is clear that (a-b) divides (a^n-b^n). So 11^n - 4^n is always divisible by 11-7, It doesn't take 10 minutes to state that.
This problem is for natural numbers so a, b, c, and n are natural numbers. If a%c=0 then a^n is divisible by c. If a%c-b%c=0, then (a^n-b^n)%c=0 and a^n-b^n is divisible by c. Example: 11%7=4 and 4%7=4. 11^13=34522712143931 and 34522712143931%7=4; 4^13=67108864 and 67108864%7=4 (11^13-4^13)=34522712143931-67108864=34522645035067 and 34522645035067%7=0, so (11^13-4^13) is divisible by 7.
I am late to the party...but...this problem is trivial using modular arithmetic. (mod 7). 11^n-4^n = 4^n-4^n (mod 7) thus equal to 0 mod 7, thus divisible by 7.
That's why there as to be a "root". It was shown first that the assumption is right for n=1. Therefore it is at least true for 1+1=2. When it's true for 2, then also for 2+1=3. And therefore for all other natural numbers. That's the beauty of induction. It's a pity that the rooting came a little short in the video.
![Prove that 7^n - 6n -1 is divisible by 36 for any natural number, n. [Mathematical Induction]](http://i.ytimg.com/vi/kNmUneld518/mqdefault.jpg)
![Prove that 7^n - 6n -1 is divisible by 36 for any natural number, n. [Mathematical Induction]](/img/tr.png)
Great work as always!
Thanks
As an IB student in grade 11 who has half-yearly examinations for Mathematics tomorrow you really made me feel smarter about myself and give me that confidence, I really respect you! I'm happy that my teacher is also good, everyone should be blessed with a teacher like you sir.
I'm an engineer and I watch a lot of science and math related videos, but I don't think I've seen this sort of divisibility proof before. Thanks for making the video! It was well explained, and I learned something new!
Easy solution using modular algebra : 11 ≡ 4 mod(7) ➔ 11^n ≡ 4^n mod(7) ➔
11^n - 4^n ≡ 0 mod(7) ➔ 11^n - 4^n is divisible by 7
Right, but induction is a way to prove that that first -> is valid:
* 11^n = 4^n mod 7 is true for n=1
* For any n, if 11^n = 4^n, then (11^n)*11 = (4^n)*4 mod 11, i.e. 11^(n+1) = 4^(n+1)
@@emurphy42 No, because the product of 2 congruences is also a congruence (rule of multiplication of congruences)!
11 ≡ 4 mod(7) and 11 ≡ 4 mod(7) ---> 11*11 ≡ 4*4 mod(7) ...
@WahranRai Sure, but that only covers the jump from n=1 to n=2. Yes, intuitively it keeps going for all n, but that's what induction -is-, it's the formal equivalent of that intuition:
* if it works for the first element of a sequence
* and if it working for any one element of that sequence implies it also working for the next element
* then it works for every element of that sequence
@@emurphy42 I told you it is not necessary to use induction.
In modular algebra you have the same operation as with integers..
x=y ---> x^n = y^n It is known and you do not have to demonstrate it by induction...
@@WahranRaiit is a well established result, but... It is not an axiom of the mathematical system. How do you think this result was proven? More precisely, how does one go about proving this well known result without induction? I am not sure you can.
I shall give a quick method using theory of binomial
(a+b)^n= a^n+nC1a^(n-1)b+.............+nCn b^n
So we can write 11^n=(7+4)^n
Now problem reduces to-
(7+4)^n-4^n
=>4^n+nC1(4^n-1)[7]+.......+7^n -4^n
So we 4^n gets cancelled and thereby every term left containes a factor of 7.
HP
Alternatively:
aⁿ-bⁿ=(a-b)(aⁿ⁻¹ + aⁿ⁻²b¹ + aⁿ⁻³b² + .... +a¹bⁿ⁻²+bⁿ⁻¹)
You can remember that as a notable product(just like you know (a+b)ⁿ is a binomial).... alternatively. let's take
S=aⁿ⁻¹ + aⁿ⁻²b¹ + aⁿ⁻³b² + .... +a¹bⁿ⁻²+bⁿ⁻¹
This is a geometric progression with factor b/a and n terms.... using the geometric sum formula:
S=aⁿ⁻¹ (1 - (b/a)ⁿ) / (1 - (b/a))
S=a(aⁿ⁻¹ - bⁿ/a) / (a - b)
S=(aⁿ - bⁿ) / (a - b)
Alternatively, using the geometric sum trick, take S and multiply by (b/a)
(b/a)S = aⁿ⁻²b¹ + aⁿ⁻³b² + .... +a¹bⁿ⁻²+bⁿ⁻¹+bⁿ/a
Subtract from S:
S - (b/a)S = (aⁿ⁻¹ + aⁿ⁻²b¹ + aⁿ⁻³b² + .... +a¹bⁿ⁻²+bⁿ⁻¹)-(aⁿ⁻²b¹ + aⁿ⁻³b² + .... +a¹bⁿ⁻²+bⁿ⁻¹+bⁿ/a)
Note how almost all terms in the RHS are the same, except aⁿ⁻¹ and bⁿ/a
S - (b/a)S = aⁿ⁻¹-bⁿ/a
(Lore: the induction is hidden on this step... this is a telescoping sum)
(1-(b/a)) S = (1/a)(aⁿ-bⁿ)
S = (1/a)(aⁿ-bⁿ) / (1-(b/a))
If you arrange it out you should arrive at the same expression back again.
The geometric sum fails at a=0... in this case
aⁿ-bⁿ=(a-b)(aⁿ⁻¹ + aⁿ⁻²b¹ + aⁿ⁻³b² + .... +a¹bⁿ⁻²+bⁿ⁻¹)
Becomes:
bⁿ=(-b)(bⁿ⁻¹)
And there also a division by 0 induced when a=b... in this case
aⁿ-bⁿ=(a-b)(aⁿ⁻¹ + aⁿ⁻²b¹ + aⁿ⁻³b² + .... +a¹bⁿ⁻²+bⁿ⁻¹)
Becomes
aⁿ-aⁿ=(a-a)(....)
0=0
Which also checks out(Bonus lore: you can use that to prove the derivative of xⁿ is nxⁿ⁻¹ if you are careful on this case)
Wow very nice proof!
I'm from morocco and I want to say that your so good as a math teacher . I undrstood the example you did and I use to apply the method in other exersises
Let it be known that Prime Newtons is a genius! Thanks so much for your crystal clear explanations, it makes understanding so much easier.
I tried on my own but got stumped after 7:15, thank you for your wonderful trick!
a-b is always a factor of a^n - b^n, using factor theorem put a^n by x^n , then putting x= b in equation x^n- b^n =0 gives 0, thus by factor theorem x-b is factor of x^n - b^n
x^n - y^n is divisible by (x-y).therefore 11^n - 4^n is divisible by 7. I did not provide a proof.
I did it like this:
n = 1:
7 | 11-4
7 | 7 ✅
n => n+1:
7 | 11^n-4^n
7 | 11^(n+1)-11*4^n
7 | 11^(n+1)-4*4^n-7*4^n since a | b and a | c a | b+c
7 | 11^(n+1)-4^(n+1) ✅
I woched many videos from different tutors but finally Ive understood this one, Tomorrow I'm writing my final exam,MSM111 ,and I believe I'm going to make it🙌
Wonderful video and a much cleaner solution than I would have used. I consider the series 11^n-4^n from 1 to k+1. Like you I started with the first term of the series 11^1-4^n=7 which is divisible by 7. Then I followed the same logic as your video for the term of the series k+1 to get to 11^k+1-4^K+1=7(11^k)-4(11^k-4^k). I noted that 11^k-4^k is of course the preceding term in my series which could be expanded using the same logic so no matter what value k+1 is you end up that 11^k=1-4^k+1=7(11^k)-4(7(11^k-1)-4(7(11^k-2)-...4(7))))) and as every term in the right hand side of the equation is a multiple of 7 it follows that the right hand side is divisible by 7
Much simpler: Since 11^n is congruent to 4^n mod 7, we have 11^n - 4^n congruent to 0 mod 7
Not everyone has had a class on congruence arithmetics
@@HarmonicEpsilonDelta Even if they haven't it wouldn't take long to understand the basics of it
wow, I have exams tomorrow. You just saved me. BTW we are from Sydney!!
Hello from LA
This has really helped! A big thank from South Africa!
Awesome and clear video!! I did not even think of breaking down that number into two different numbers.
We can also use Binomial to prove this. Let 11^n = (7 + 4)^n = 7^n+ ....+4^n. After the last term is subtracted, the remaining terms all have factor 7.
this one is straight out of an advanced calculus book haha! it is a problem in chapter one of Kenneth A. Ross: Analysis the Theory of Calculus -- love it!
Another method is to multiply P(k) by (11+7)
P(k)*(11+7) = (11^k - 7^k)*(11+7) = (11+7)(11-7)m
11^(k+1) + 11^k.7 - 11.7^k - 7^(k+1) = (11-7)(11+7)m
11^(k+1) - 7^(k+1) = (11-7)(11+7)m + 11*7^k - 7*11^k
P(k+1) = (11-7)(11+7)m + 11*7^k - 7*11^k
The first term (11-7)(11+7)m is obviously divisible by 11-7 so we need to focus on 11*7^k - 7*11^k
Since 7 and 11 are factors of both remaining terms we can rewrite
11*7^k - 7*11^k = 7 *11*[ 7^(k-1) - 11^(k-1) ]
We notice that 7^(k-1) - 11^(k-1) is P(k-1) so the final formula is
P(k+1) = (11-7)(11+7)m + 7*11*P(k-1)
And of course, that method requires to manually verify the first TWO steps P(1) and P(2).
This could be a one line proof as 11^n-4^n is 4^n-4^n=0 in Z/7Z. More generally n^k-m^k=m^k-m^k=0 in Z/(n-m)Z.
Binomial theorem also works. Split 11^n into (7+4)^n and use the theorem to split it up to a sum of (7^i * 4^(n-i)) with some other factorials and crap. When i=0, the 0th term becomes 4^n and every term after is a multiple of 7. 4^n is cancelled out by the original 4^n we had, so we're only left with a sum of terms that are all multiples of 7, which means they're always going to be divisible by 7.
a^n -b^n is always divisible by (a-b) if a,b,n are integers.
Proof:
Assume a^k - b^k be divisble by (a-b). That means,
a^k - b^k = (a-b)m where m is an integer ....... Eqn. (1)
Now a^(k+1) - b^(k+1) = a.a^k - b.b^k
That is, a^(k+1) - b^(k+1) = (a-b+b)a^k - b.b^k
That is, a^(k+1) - b^(k+1) = (a-b)a^k +b.a^k - b.b^k
That is, a^(k+1) - b^(k+1) = (a-b)a^k+b(a^k - b^k)
That is, a^(k+1) - b^(k+1) = (a-b)a^k +b(a-b)m substituting a^k - b^k with Eqn.(1)
That is, a^(k+1) - b^(k+1) = (a-b)(a^k+b.m);
Hence, a^(k+1) - b^(k+1) is divisible by (a-b)
Therefore, by Mathematical induction a^n-b^n is divisible by (a-b) if a,b,n are integers.
take the first natural n=1:
11-4=7 , divisible by 7
suppose that when n=k, 11ˆk-4ˆk=7m
then test to n=k+1
11^(k+1)-4^(k+1)
11.11^k-4.4^k
(7+4).11^k-4.4^k
4(11^k-4^k)+7.11^k
4.7m+7.11^k is always divisible by 7 (k, m are integers)
We can do better. There's nothing special about 11 and 4 here.
Claim: a^n - b^n is divisible by a - b for any positive integer n.
Base case: n = 1. If n = 1, then a^n - b^n = a^1 - b^1 = a - b. And a - b is divisible by a - b.
Inductive case: Assume it's true for n = k, so a^k - b^k = (a-b)m. Consider the case when n = k+1.
a^(k+1) - b^(k+1) = a^k . a - b^k . b = (a - b + b) a^k - (b) b^k = (a - b) a^k + b . a^k - b . b^k = (a - b) a^k + b (a^k - b^k) = (a - b) a^k + b ((a - b) m) = (a - b) (a^k + bm). Since a^k and bm are both integers, we know that (a - b) (a^k + bm) is divisible by (a - b), so a^(k+1) - b^(k+1) is divisible by (a - b).
with the congruence principle, we can subsitute any number in any step with a value congruent mod 7. So we can write the thesis as the following expression 11^n - 4 ^n = 0 mod 7, because 11 = 4 mod 7 we obtain 4 = 4 mod 7 that is true.
11 is congruent to 4 mod 7, so 11^n is congruent to 4^n mod 7 and 11^n - 4^n is congruent to 4^n - 4^n = 0 mod 7, and that's finished.
Lovely video. Like the cap..
I wish you had been my math teacher when I was a kid.
Are you blaming your previous math teachers?
BASE CASE: 0
11^0 - 4^0 = 0 = 7(0) P(k + 1), by mathematical induction, P(n) must be true for all n where n is contained within the set of natural numbers.
Just discovered your channel. Really good content. Keep it up. ❤
Solution:
Test:
11² - 4²
= (11 - 4)(11 + 4)
= 7 * 15
→ verified
Assumption: (with x being an integer)
11^n - 4^n = 7x
Iteration: Looking for an integer y
11^(n + 1) - 4^(n + 1) = 7y
11^n * 11 - 4^n * 4 + 4^n * 7 - 4^n * 7 = 7y
11^n * 11 - 4^n * 11 - 4^n * 7 = 7y
11 * (11^n - 4^n) - 4^n * 7 = 7y
11 * 7x - 4^n * 7 = 7y
7 * (11x - 4^n) = 7y |:7
11x - 4^n = y
Since x is an integer and 4^n → verified
Just write 11^n=(7+4) ^n and use binomial expansion. In third line you can prove the required thing.
I like this one. Just one line.
for even numbers, it's divisible by 7 (because 11²-4²=(7)(15) and 11⁴-4⁴=(121-16)(121+16)=(105)(137)=(7)(15)(137)) and for numbers that are divisible by 3, it's also divisible, but i don't know how with primes (sorry for bad english)
11^n is (7 + 4)^n. Every element in this polynomial, except for the last, is multiplied by 7 at least once, making it so only the last one (which is 4^n), isn't divisible by 7. This one cancels out with -4^n, making 11^n - 4^n divisible by 7.
A^n - B^n is always divisible by A-B. Even n is obvious, odd n more difficult.
For any positive integer n, aⁿ - bⁿ = (a - b)(aⁿ⁻¹b⁰ + aⁿ⁻²b¹ + aⁿ⁻³b² + aⁿ⁻⁴b³ + ... + aⁿ⁻ⁿbⁿ⁻¹). This factorization is valid for both odd and even n.
More fun with math: For any *odd* positive integer n, aⁿ + bⁿ is divisible by a + b by the factorization aⁿ + bⁿ = (a + b)(aⁿ⁻¹b⁰ - aⁿ⁻²b¹ + aⁿ⁻³b² - aⁿ⁻⁴b³ + ... + aⁿ⁻ⁿbⁿ⁻¹). Not for even n, however.
Binomial expansion approach avoids having to be concerned about the parity of n.
(B+km)^n = B^n+(n¦1) B^(n-1) km+(n¦2) B^(n-2) (km)^2+⋯+(km)^n congruent to B^n (mod m)
😮 ¡awesome exercise! 👍
so helpful, thank you!!!!
so good--so satisfying!
a^n-b^n=(a-b)(a^(n-1)*b^0 + a^(n-2)*b^1 + ...+a^(n-k-1)*b^k + ... +b^(n-1) )=> 11^n - 7^n = 7*(11^(n-1) + ...+ 7^(n-1) ) = 7 * (...) -> divisible by 7
Induction is overkill for this problem.
11 ≡ 4 modulo 7, so (11^n - 4^n) ≡ (4^n - 4^n) ≡ 0 modulo 7 QED
(11^n - 4^n) ≡ (4^n - 4^n) follows from the Binomial theorem which holds ∀ n ∈ N(This is why induction is unnecessary)
One man's overkill is another man's natural way to do it. The purpose of the video was probably to show how it can be done without knowing modular arithmetic nor additional theorems.
@@ingo-w modular arithmetic is a fancy phrase for basic integer divisibility properties. Integer divisibility is easier than induction which is not usually taught in high school. Many first learn about induction in a graduate level number theory course.
It's been over a decade since I've done math at this level, but wouldn't you be able to do it more simply with log?
yep it is easy
induction starts from n = 1 : 11 - 4 = 7
in 11^n - 4^n div 7, view
11*11^n - 4*4^n = 11*11^n -4*11^n + 4 * 11^n - 4*4^n (added and substracted 4*11^n )=
11^n (11-4) - 4(4^n - 11^n).
if 4^n - 11^n div 7, then whole expression what is equal to 11*11^n - 4*4^n is div 7
You need to either prove that it is true for the kth instance of 11^k - 7^k, or show a proper relation between the 1st instance and the kth, then your proof is done (for positive integer instances). While you might say this is implicit from the 1st term, it isn't explained clearly in your proof. The point of a proof isn't just to have the correct assumption but also to show how/why it is true. Like others said, this can be proven with binomial expansion. Induction isn't needed.
Thank you so much sir
But the first number of N is 0 not 1.
The beginning of the proof by induction must be with 0 not 1
Not necessarily. You can start the induction with any n you want, but of course you have to show also that it holds for numbers that are lower than n. Which is in this case particularly easy with n=0.
@@ingo-w No. You must necessary do the verification by 0. Necessary
@@YoussefSaydi No. Suppose you didn't see that it holds for all natural numbers and thought that it holds only for natural numbers > 0. Then you would start the induction with 1, just like in the video. Then you obtain a valid proof that the proposition holds for all n > 0. Add to this the trivial observation that it holds for n = 0 also and you have the proof that it holds for all natural numbers. In the same way, you could start the induction with, say, n=3 and then proove it for n in 0,1,2 afterwards to reach a valid proof that it holds for all natural numbers. Though I wouldn't do it that way but start with n=0 like you suggest, but it's valid proofs nevertheless just a bit more complicated since you need the extra proofs for the lower ns.
The first natural number is 1 not 0
@@fauzant453 in N*
Let's expand: m = (11^k - 4^k)/7 --> 11^(k+1) - 4^(k+1) = 7*11^k + 7*4m = 7*11^k + 7*4(11^k - 4^k)/7 = 7*11^k + 4(11^k - 4^k) = 7*11^k + 4*11^k - 4*4^k = 11*11^k - 4*4^k = 11^(k+1) - 4^(k+1) QED
(x-y) is *always* a factor of x^n-y^n. It’s just well-known Highschool algebra.
(a+b)^n mod a = b^n mod a
so, 11^n mod 7 = 4^n mod 7
11^n - 4^n mod 7 = 0
Hello sir ❤, thanks for this video
I have a doubt, 'm' will never be a -ve number and zero.
Then why are you saying 'm' is an integer 😂. I will say 'm' is a natural number. If you say that both are correct then I will say 'm' is a Complex numbers( set of all kinds of numbers 😂😂😂😂😂). If you say a natural number then problem solved.
Other wise it is a debatable topic 😂😂. anyway thank you sir for this video.
My poor English hop you understand 😁
Also:
2^(2(2n+1)) + 1 is divisible by 5 for all n >= 0
2^(4(2n+1)) + 1 is divisible by 17 for all n >= 0
😊
11-4=7, This is the core reason...
No not true
@@eagleeagle7971it is true because a^n - b^n is divisible by a-b for all positive integers n
not necessarily
It is. Next step is to prove that that holds for powers of it.
That's core reason, but not proof.
Because 11^n-4^n = (11-4)E k=0 --> n-1 11^k*4^n-1-k
Thank you sir
I used the remarkable identity (a^n -b^n ) to prove that ( 11^n - 4^n) is a multiple of 7 so we can wright it as 7*k wich k is a natural number
I see. It makes sense to to relate a^n-b^n=(a-b)(a^(n-1)+a^(n-2)b+...+b^(n-1))
I wanted to use binomial expansion by writing 11^n-4^n=(7+4)^n-4^n = choose(n,k)*7^(n-k)*4^k -4^k . So 4^n cancel out and we are left with all the terms for k from 0 to n-1 which all contain a multiple of 7. Qed
My thought went to a problem I knew before:
Show that fraction
(2^(n+3) + 3^n*5^(n+1))/(2^(n+2)×3^(n+1)+5^(2n)) Is always reductible by 13
11 equivalent 4 mod 7
Done.
But how we proof assumption of Pk?
Unfortunately this came a little short in the video.
It was shown for n=1. So the assumption is right for 1, therefore also right for 2. And when it's right for 2, then it's also right for 3 - and so on.
It is even true (trivially) for n=0.
Wow
Sorry, but this is trivial. Since a^n - b^n = (a - b)( a^(n-1) + a^(n-2)b + a^(n-3)b^2 + ... +ab^(n-2) + b^(n-2) ), it is clear that (a-b) divides (a^n-b^n). So 11^n - 4^n is always divisible by 11-7,
It doesn't take 10 minutes to state that.
E = (7 + 4)ⁿ - 4ⁿ = 7ⁿ + 7ⁿ⁻¹4¹k₁+ ... + 7¹4ⁿ⁻¹kₙ₋₁
so E is clearly divisible by 7
You need to be more specific about the set of natural numbers. a^0 = 1.
This problem is for natural numbers so a, b, c, and n are natural numbers.
If a%c=0 then a^n is divisible by c. If a%c-b%c=0, then (a^n-b^n)%c=0 and a^n-b^n is divisible by c.
Example: 11%7=4 and 4%7=4. 11^13=34522712143931 and 34522712143931%7=4; 4^13=67108864 and 67108864%7=4
(11^13-4^13)=34522712143931-67108864=34522645035067 and 34522645035067%7=0, so (11^13-4^13) is divisible by 7.
Stop using a percent symbol for the intended operation.
I am late to the party...but...this problem is trivial using modular arithmetic. (mod 7). 11^n-4^n = 4^n-4^n (mod 7) thus equal to 0 mod 7, thus divisible by 7.
ab mod x = ((a mod x)(b mod x)) mod x. Since 11 mod 7 = 4, 11^n mod 7 = 4^n mod 7.
11 = 4 mod 7
11^n = 4^n mod 7
11^n - 4^n = 0 mod 7
so it is divisible
proof by modular arithmetic:
11 = 4
so 11^n - 4^n = 0
ez qed
(11^n - 4^n)mod 7=(4^n - 4^n)mod7=0 mod 7
I knew strait away what was the giant X . It’s twitter
overkill it with zsigmondy's theorem next
You can't use assumptions for your proof. This is a case of a circular reasoning
That's why there as to be a "root". It was shown first that the assumption is right for n=1. Therefore it is at least true for 1+1=2. When it's true for 2, then also for 2+1=3. And therefore for all other natural numbers. That's the beauty of induction.
It's a pity that the rooting came a little short in the video.
your writing board is so bright that the writing is invisible donot what are you writing
0 is not a solution!
Yes it is
👎