Is 8^n+47 never a prime? Why? | JBMO Shortlist

[@amitsrivastava1934]

An excellent problem with an elegant solution.

[@shinoa8605]

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

[@gabiturbinca9102]

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

[@magicmeatball4013]

Now prove fermats theorem

[@霍金本人]

@@magicmeatball4013 Google is your best friend

[@ignaciobenjamingarridoboba2071]

@@magicmeatball4013 the induction proof is not hard

[@zhangmike4852]

the solution is amazingly simple!

[@kobethebeefinmathworld953]

For Claim #2, I'll suggest using Fermat's little theorem to make the proof shorter and cleaner.

[@mahmoudalbahar1641]

Thank your for great videos... And I suggest that you make video about combinatorial proof for Hexagon identity in pascal triangle.

[@goatgamer001]

if 8^n is 1 mod 3, then its pretty obvious. if it isnt, it is either divisible by 5 or 13.

[@9core]

yeah this type of problem is almost always easily solvable using that method

[@9core]

yeah this type of problem is almost always easily solvable using that method

[@johnnath4137]

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]

For odd case why didn’t we just do 2m+1?

[@johnnath4137]

@@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).

[@lgooch]

@@johnnath4137 ah thanks

[@leif1075]

@@johnnath4137 but 47 equals 2 mod 3 not zero mod 3?

[@johnnath4137]

@@leif1075 1 + 47 = 48 ≡ 0 (mod 3).

[@richardfredlund3802]

with the heavy hint re divisibility by 3,5,13 I twigged how to do this by about minute 7.

[@bait6652]

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

[@azai.mp4]

Great example of how trying out small values can help you come up with a proof!

[@pandagameryt6288]

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.

[@amagilly]

Another masterpiece.

[@krishnanadityan2017]

When n is even, the given number is divisible by 3.

[@SQRTime]

Hi Krishnan. If you are interested in math competitions, please consider kzbin.info/www/bejne/r6C1dp-gq6x_pa8 and other videos in the Olympiad playlist. Hope you enjoy 😊

[@paulchapman8023]

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.

[@maelmao]

What’s the tablet you use ?

[@snehasismaiti342]

I can't do this problem can anyone solve this "Find the smallest number which has 144 divisors 10 of which are consecutive number."

[@kyooz4776]

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

[@snehasismaiti342]

@@kyooz4776 why 3n-1 as exponent of 2 terms

[@leif1075]

@@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?

[@kyooz4776]

@@leif1075 read again

[@kyooz4776]

@@snehasismaiti342 because there are 144 divisors, search up number of divisors formula

[@dimitardimitrakov2841]

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.

[@sirak_s_nt]

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.

[@ReckonClasses]

Nice question

[@ElmanMaharramov]

Where can you found this question? Please tell me it

[@ibrahimagazade9418]

😅😅

[@ElmanMaharramov]

@@ibrahimagazade9418 tapdın burdada məni😅

[@xeyalehemzeyeva08]

😂

[@euleri0]

Indigenous!! ⭐

[@Szynkaa]

tbh awful question, typical checking modulo prime numbers and praying to god for it to work without checking too many of them

[@SQRTime]

Hi Mr Sz. If you are interested in math competitions, please consider kzbin.info/www/bejne/r6C1dp-gq6x_pa8 and other videos in the Olympiad playlist. Hope you enjoy 😊

[@muhendisgenc8216]

Woooow

[@SQRTime]

Hi. If you are interested in math competitions, please consider kzbin.info/www/bejne/r6C1dp-gq6x_pa8 and other videos in the Olympiad playlist. Hope you enjoy 😊

[@ElieBensaid]

14 mins just to study that number in 3 different mods, kind of a waste of time

[@aftorucova9980]

Does anyone have JBMO 2022 shortlist?

[@wookong1723]

loveeeeeeee

[@amirhosseinmohajerinejad1393]

Nice

[@atpugnes]

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.

[@sdspivey]

He isn't multiplying, he's just copying the result he already calculated.

[@bornfromstardust1526]

The method is called, Calculator Inclusion method.

[@poproporpo]

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.

[@EternalLoveAnkh]

I don't mean to criticize but wouldn't it be easier to ask if it is ever prime? RJ

[@Sp1tz1fy]

For photo math, it turns out as a exponential function

[@Ming-pt6wt]

photo math can't do number theory questions.

[@王剛-m7n]

3.5.13 mod cover 2n，4n+1, 4n+3

[@JinhaoPan-np7zy]

写过

[@xeyalehemzeyeva08]

Would you please tell me where to find it?

[@ElmanMaharramov]

Məndə soruşmuşam hələ cavab vermiyib

[@xeyalehemzeyeva08]

@@ElmanMaharramov deyəsən vermiyəcək..

[@joaozin003]

n=-infinity

[@hijeffhere]

What app are you using to write these? Thank you!

[@browhat6935]

Try latex codecogs

[@typo691]

it's onenote, he wrote in a community post once

[@hijeffhere]

Thank you, people!

[@donaldcoombs79]

donnkey kong mario cart

[@haleshs66]

13:06 How can 4096^k always have a remainder of 1 when divided by 13 ???

[@crazycat1503]

When you multiply numbers, their remainders also multiplies

[@mcwulf25]

(4095+1)*(4085+1)*.... where 13|4095. Multiply out the brackets and each term apart from the 1*1*1*... is divisible by 13.

[@hhgygy]

@@mcwulf25 Thanks I also missed that step why 64k would always yield a remainder of 1

[@leif1075]

@@mcwulf25 where did you get 4095 from? And why out the extra 1 there?

[@mcwulf25]

@@leif1075 All I am doing is replacing 4096 with 4095+1. That 4085 should be 4095.

[@iDovahkiin]

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??

[@ervinforever9953]

The word **only** is the key. 55 is divisible with 5 and 11 as well.

[@iDovahkiin]

@@ervinforever9953 how did i not realize 🤦

[@leif1075]

Isn't there a way tonsolve without using mod??

[@adb012]

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".

[@adb012]

@@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.

[@dimitardimitrakov2841]

yes, i wrote it in the comments, if you use odd vs even.

[@mr.kaiden7159]

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

[@yoav613]

Why are you negative? Ask is 8^n+47 always composite,and be positive!

[@ReckonClasses]

Nice question