If u use fermats theorem u get that 8^4k=1mod 5 from which 8^(4k+1)+47=8+47=0mod 5, and also 8^4k=2^12k=1mod 13,from which 8^(4k+3)+47=512+47=0mod 13 n even its pretty easy to show that 8^n+47=1+47=0 mod 3
If n is even let n = 2m. We have 8*n + 47 = 64^m + 47 ≡ 1^m + 47 (mod 3) ≡ 0 (mod 3) ⇒ 3|(8^n + 47) for even n. If n is odd, there are two cases (i) n = 4m + 1 or (ii) n = 4m + 3. Case (i): 8^n + 47 = (4)(256^m) + 47 ≡ (4)(1^m) + 47 (mod 17) ≡ 0 (mod 17) ⇒ 17|(8^n + 47) for odd n of form 4m +1 Case (II): 8^n + 47 = (64)(256)^m + 47 ≡ (1)(1^m) + 47 (mod 3) ≡ 0 (mod 3) ⇒ 3|(8^n + 47) for odd n of form 4n + 3. Thus 8^n + 47 is composite for all n.
@@lgooch Because there are two types of odd numbers, type 4m + 1 and type34m + 3, and "2n + 1" doesn't discriminate between them. And each type requires a different argument. I'll illustrate further by a nice example. Every prime of the form 4m + 1 can be expressed as the sum of two integer squares but no prime of the form 4m + 3 can be so expressed (a result due to Fermat).
we know that for a prime p>=7, p=1,-1 (mod 6). if 8^n +47 is a prime, then 8^n +47 = +1,-1 (mod 6). but 8^N+47 = 2^n -1 which should be =1,-1 (mod6). since -1 is is impossible, we take 1. so, 2^n= 2 (mod 6). 2^n-1 =1 mod6. which is never possible for n>=1and the given eq implies p>=55. so, 8^n +47 is never a prime.
Hi Krishnan. If you are interested in math competitions, please consider ua-cam.com/video/yoREljvGLoM/v-deo.html and other videos in the Olympiad playlist. Hope you enjoy 😊
110880=2⁵×3²×5×7×11 notice that because you need to have 10 consecutive divisors at least one of them has to be divisible by 8=2³ and another one by 9=3². You then want to have the smallest primes possible in the factorization of this number. Because 144=2⁴×*3²* two terms will have exponent 3n-1. You can then either have 2³×3^(3-1)×5^(3-1)×7×11 which has 4×3×3×2×2=144 divisors or 2^(6-1)×3^(3-1)×5×7×11 which also has 6×3×2×2×2=144 divisors. The second one is smaller so the answer is 110880
@@kyooz4776 but the problem as stated doesn't make sense..144 divisors of 10..10 only has 4 divisors 1,2,5 and 10..and what does he mean consecutive numbers?
Hi Mr Sz. If you are interested in math competitions, please consider ua-cam.com/video/yoREljvGLoM/v-deo.html and other videos in the Olympiad playlist. Hope you enjoy 😊
Proof by contradiciton without mods: 8^n + 64 - 17 = p where p is prime p>=55 and n>2 . Then 8^(n-2)+1 = (p+ 17)/64. left hand side is odd. In the right hand side p is odd because prime => p+17 is even . let p+17 = 2k. Then right hand side becomes k/32 and it must be odd because left hand side is odd. therefor k is odd and let k=2t+1. Finally we have 32*8^(n-2) + 32 = 2t+1 => something even = 2t - 31 which is odd.
You cannot claim that k is odd. Even though k/32 is odd, k can be 96 for which k/32 is odd. Use your common sense, if k is odd, how come 32 is going to reduce it to an integer? 32 cannot divide odd numbers.
Yes, even though he most likely copied computations that he had previously completed, there are mental math calculation methods that allow you to calculate from the most significant digit to the least significant digit. As you calculate, you would have to go back and change the result that you have already completed if you need to carry digits. Many mental arithmetic competitors prefer this method iirc.
Yes. The same way. Just use division and remainder. For example, instead of saying "note that 64^k is 1 (mod 3)" say "note that if you divide 64^k by 3 you get a remainder of 1, because 63 is multiple of 3".
@@adityaekbote8498 ... Given that the question is asking if something is prime, and prime means that it is only divisible by itself and 1, and divisible means that the reminder of the division is zero, I doubt that it can be proved without using this concept. You can disguise it as "being in the time table of...", or doing repeated subtractions instead of dividing, or stuff like that. But at the end of the day, to show that something is NEVER prime you need to show that is ALWAYS divisible by something other than itself and 1.
You mean: "Is 8^n+47 is always prime"? Idk if I'm wrong but aren't a prime number is a number that is only dividable by itself and 1? So 8+47=55 which is a prime number??
Hi. If you are interested in math competitions, please consider ua-cam.com/video/yoREljvGLoM/v-deo.html and other videos in the Olympiad playlist. Hope you enjoy 😊
If u don't know fermat's theorm U can use (a+b)^n =b^n MOD a we divide into four case for n=4k+i,for k=0,1,2,3,... and i=0,1,2,3 Now, we know that's number is odd ans 47=-1 MOD 3 47=2 MOD 5 47=-2 MOD 7 47=2 MOD 9 47= 3 MOD 11 47= -5 MOD 13 For case i=0,2 8^(4k+i)=(9-1)^(4k+i) Because i is even and 3|9 then 8^(4k+i)=1 MOD 3 For i=1 so 4k+1 is odd 8^(4k+1)=(10-2)^(4k+1)=-2 MOD 5 For i=3 so 4k +3 is odd 8^(4k+3)=(13-5)^(4k+3)=(-5)^(4k+3) MOD 13=(-5)((26-1)^(2k+1)) MOD 13=(-5)(-1) MOD 13=5 MOD 13 So 8^n+47 always can divided by 3,5,or 13
An excellent problem with an elegant solution.
the solution is amazingly simple!
If u use fermats theorem u get that 8^4k=1mod 5 from which 8^(4k+1)+47=8+47=0mod 5, and also
8^4k=2^12k=1mod 13,from which 8^(4k+3)+47=512+47=0mod 13
n even its pretty easy to show that 8^n+47=1+47=0 mod 3
Now prove fermats theorem
@@magicmeatball4013 Google is your best friend
@@magicmeatball4013 the induction proof is not hard
Thanks a lot, sir, for your work. I am seeing, how I become better everyday. This is the result of your work as well as mine
For Claim #2, I'll suggest using Fermat's little theorem to make the proof shorter and cleaner.
Thank your for great videos...
And I suggest that you make video about combinatorial proof for Hexagon identity in pascal triangle.
if 8^n is 1 mod 3, then its pretty obvious. if it isnt, it is either divisible by 5 or 13.
yeah this type of problem is almost always easily solvable using that method
yeah this type of problem is almost always easily solvable using that method
Interesint authoer typically likes to play with smaller modulo/negative...but calculated 64^2....instead of just using 64(1,-1,1,-1,1)for %3,5,13
with the heavy hint re divisibility by 3,5,13 I twigged how to do this by about minute 7.
If n is even let n = 2m. We have 8*n + 47 = 64^m + 47 ≡ 1^m + 47 (mod 3) ≡ 0 (mod 3) ⇒ 3|(8^n + 47) for even n. If n is odd, there are two cases (i) n = 4m + 1 or (ii) n = 4m + 3. Case (i): 8^n + 47 = (4)(256^m) + 47 ≡ (4)(1^m) + 47 (mod 17) ≡ 0 (mod 17) ⇒ 17|(8^n + 47) for odd n of form 4m +1 Case (II): 8^n + 47 = (64)(256)^m + 47 ≡ (1)(1^m) + 47 (mod 3) ≡ 0 (mod 3) ⇒ 3|(8^n + 47) for odd n of form 4n + 3. Thus 8^n + 47 is composite for all n.
For odd case why didn’t we just do 2m+1?
@@lgooch Because there are two types of odd numbers, type 4m + 1 and type34m + 3, and "2n + 1" doesn't discriminate between them. And each type requires a different argument. I'll illustrate further by a nice example. Every prime of the form 4m + 1 can be expressed as the sum of two integer squares but no prime of the form 4m + 3 can be so expressed (a result due to Fermat).
@@johnnath4137 ah thanks
@@johnnath4137 but 47 equals 2 mod 3 not zero mod 3?
@@leif1075 1 + 47 = 48 ≡ 0 (mod 3).
we know that for a prime p>=7, p=1,-1 (mod 6). if 8^n +47 is a prime, then 8^n +47 = +1,-1 (mod 6). but 8^N+47 = 2^n -1 which should be =1,-1 (mod6). since -1 is is impossible, we take 1. so, 2^n= 2 (mod 6). 2^n-1 =1 mod6. which is never possible for n>=1and the given eq implies p>=55. so, 8^n +47 is never a prime.
When n is even, the given number is divisible by 3.
Hi Krishnan. If you are interested in math competitions, please consider
ua-cam.com/video/yoREljvGLoM/v-deo.html and other videos in the Olympiad playlist. Hope you enjoy 😊
Every power of 4 is two less than a multiple of 3, every power of 64 is also a power of 4, and 47 mod 3 = 2. Yup, that checks out.
I can't do this problem can anyone solve this "Find the smallest number which has 144 divisors 10 of which are consecutive number."
110880=2⁵×3²×5×7×11
notice that because you need to have 10 consecutive divisors at least one of them has to be divisible by 8=2³ and another one by 9=3². You then want to have the smallest primes possible in the factorization of this number. Because 144=2⁴×*3²* two terms will have exponent 3n-1. You can then either have
2³×3^(3-1)×5^(3-1)×7×11 which has 4×3×3×2×2=144 divisors or 2^(6-1)×3^(3-1)×5×7×11 which also has 6×3×2×2×2=144 divisors. The second one is smaller so the answer is 110880
@@kyooz4776 why 3n-1 as exponent of 2 terms
@@kyooz4776 but the problem as stated doesn't make sense..144 divisors of 10..10 only has 4 divisors 1,2,5 and 10..and what does he mean consecutive numbers?
@@leif1075 read again
@@snehasismaiti342 because there are 144 divisors, search up number of divisors formula
interesting property that Ax ≡ 1 mod (x-1)
Great example of how trying out small values can help you come up with a proof!
Another masterpiece.
What’s the tablet you use ?
Where can you found this question? Please tell me it
😅😅
@@ibrahimagazade9418 tapdın burdada məni😅
😂
Does anyone have JBMO 2022 shortlist?
I don't mean to criticize but wouldn't it be easier to ask if it is ever prime?
RJ
3.5.13 mod cover 2n，4n+1, 4n+3
13:06 How can 4096^k always have a remainder of 1 when divided by 13 ???
When you multiply numbers, their remainders also multiplies
(4095+1)*(4085+1)*.... where 13|4095. Multiply out the brackets and each term apart from the 1*1*1*... is divisible by 13.
@@mcwulf25 Thanks I also missed that step why 64k would always yield a remainder of 1
@@mcwulf25 where did you get 4095 from? And why out the extra 1 there?
@@leif1075 All I am doing is replacing 4096 with 4095+1.
That 4085 should be 4095.
tbh awful question, typical checking modulo prime numbers and praying to god for it to work without checking too many of them
Hi Mr Sz. If you are interested in math competitions, please consider
ua-cam.com/video/yoREljvGLoM/v-deo.html and other videos in the Olympiad playlist. Hope you enjoy 😊
Proof by contradiciton without mods: 8^n + 64 - 17 = p where p is prime p>=55 and n>2 . Then 8^(n-2)+1 = (p+ 17)/64. left hand side is odd. In the right hand side p is odd because prime => p+17 is even . let p+17 = 2k. Then right hand side becomes k/32 and it must be odd because left hand side is odd. therefor k is odd and let k=2t+1. Finally we have 32*8^(n-2) + 32 = 2t+1 => something even = 2t - 31 which is odd.
You cannot claim that k is odd. Even though k/32 is odd, k can be 96 for which k/32 is odd.
Use your common sense, if k is odd, how come 32 is going to reduce it to an integer? 32 cannot divide odd numbers.
For photo math, it turns out as a exponential function
photo math can't do number theory questions.
Would you please tell me where to find it?
Məndə soruşmuşam hələ cavab vermiyib
@@ElmanMaharramov deyəsən vermiyəcək..
I am little curious. Whenever you multiply, you start from the most significant digit. How is it so? Normally we would start from units place.
He isn't multiplying, he's just copying the result he already calculated.
The method is called, Calculator Inclusion method.
Yes, even though he most likely copied computations that he had previously completed, there are mental math calculation methods that allow you to calculate from the most significant digit to the least significant digit. As you calculate, you would have to go back and change the result that you have already completed if you need to carry digits. Many mental arithmetic competitors prefer this method iirc.
14 mins just to study that number in 3 different mods, kind of a waste of time
Nice question
Isn't there a way tonsolve without using mod??
Yes. The same way. Just use division and remainder. For example, instead of saying "note that 64^k is 1 (mod 3)" say "note that if you divide 64^k by 3 you get a remainder of 1, because 63 is multiple of 3".
@@adityaekbote8498 ... Given that the question is asking if something is prime, and prime means that it is only divisible by itself and 1, and divisible means that the reminder of the division is zero, I doubt that it can be proved without using this concept. You can disguise it as "being in the time table of...", or doing repeated subtractions instead of dividing, or stuff like that. But at the end of the day, to show that something is NEVER prime you need to show that is ALWAYS divisible by something other than itself and 1.
yes, i wrote it in the comments, if you use odd vs even.
What app are you using to write these? Thank you!
Try latex codecogs
it's onenote, he wrote in a community post once
Thank you, people!
donnkey kong mario cart
You mean:
"Is 8^n+47 is always prime"?
Idk if I'm wrong but aren't a prime number is a number that is only dividable by itself and 1?
So 8+47=55 which is a prime number??
The word **only** is the key. 55 is divisible with 5 and 11 as well.
@@ervinforever9953 how did i not realize 🤦
Indigenous!! ⭐
n=-infinity
Nice
Woooow
Hi. If you are interested in math competitions, please consider
ua-cam.com/video/yoREljvGLoM/v-deo.html and other videos in the Olympiad playlist. Hope you enjoy 😊
loveeeeeeee
Why are you negative? Ask is 8^n+47 always composite,and be positive!
写过
If u don't know fermat's theorm
U can use (a+b)^n =b^n MOD a
we divide into four case for n=4k+i,for k=0,1,2,3,... and i=0,1,2,3
Now, we know that's number is odd ans
47=-1 MOD 3
47=2 MOD 5
47=-2 MOD 7
47=2 MOD 9
47= 3 MOD 11
47= -5 MOD 13
For case i=0,2
8^(4k+i)=(9-1)^(4k+i)
Because i is even and 3|9 then 8^(4k+i)=1 MOD 3
For i=1 so 4k+1 is odd
8^(4k+1)=(10-2)^(4k+1)=-2 MOD 5
For i=3 so 4k +3 is odd
8^(4k+3)=(13-5)^(4k+3)=(-5)^(4k+3) MOD 13=(-5)((26-1)^(2k+1)) MOD 13=(-5)(-1) MOD 13=5 MOD 13
So 8^n+47 always can divided by 3,5,or 13
Nice question