When can 101010...1 be prime? Putnam exam 1989
Vložit
- čas přidán 29. 06. 2024
- This question is from the Putnam exam in 1989.
Can you find a prime factor for this BIG number? • Prime factor 100200400...
Check out more fun math competition problems: • A circle tangents to a...
🛍 Shop my math t-shirt & hoodies: amzn.to/3qBeuw6
💪 Get my math notes by becoming a patron: / blackpenredpen
#blackpenredpen #math #calculus #apcalculus
Nobody:
BPRP: 101, this is not lol, be careful.
101st like ;D
Btw Numberphile also had a video where 101 in binary is the only “cyclops prime”
Numberphile video:
m.czcams.com/video/HPfAnX5blO0/video.html
This was a question in the 1989 Putnam Competition! I participated in the Competition, but I couldn't solve this. The answer popped into my head a year later, when I was studying for the 1990 Competition. Too late!
Sad!
I'll be completely honest, it took me until you said "100-1=99" for me to realize you weren't doing this in binary lol
it doesn't matter if he was anyways the same logic applies
The divide by 3 trick doesn't work in binary.
@@oida10000 Incorrect; or at least, not really. The system is actually (all ones) in base 4. The 3 trick works in base 4 for the exact same reason that the 9 trick works in base 10, namely that it is a factor of the base less 1.
So in base 4, the base 10 divisibility rules for both 9 and 11 convert directly into divisibility rules for 3 and 5, respectively one less than and one more than the base.
Thus it's readily seen that, for a string of 1's in base 4, N is divisible by 5 if n is even and is divisible by 3 exactly when n is divisible by 3.
But this is independent of the problem base. When the problem is stated in base is 10 we have a string of all 1's in base 100; and again N is divisible by 3 since 3 divides 100-1 = 99) exactly when n is, and is divisible by 101 = 100 + 1 exactly when n is even.
i thought that bunny is your new microphone
We all know he stuffed the giant microphone inside of it
Bold of you to assume it isn't one, Cotton.
@@jamiecjx5606 it ate the big microphone
He is wearing a Lav mic :/
The bunny-phone is new technology, though with a twist. See it has rabbit ears, much like the old TVs we all had many years ago.
The lockdown is affecting you, you're talking to a bunny
You don't talk to bunnies when you're on lockdown?
lol
I only talk to bunnies when I am alone. This means that it's actually more frequent during lockdown.
To be fair, from BPRP's POV that bunny is more real than any of us 🤔🤣
I talk to bunnies too {()} 😛
I thought it's in binary...
I did as well. Was getting confused for a while.
ya also ... but appreciate it
me as well!!!
The same type of deduction applies, but using 4 and 2 instead of 100 and 10, respectively. The result is exactly the same, though. In fact, the result holds in any integer base larger than 1. 1 + x^2 ••• + x^(2n - 2) + x^(2n) = N = (x^(2(n + 1)) - 1)/(x^2 - 1), which implies x^2 - 1, which is a natural number if x is a positive integer, equals (x^(n + 1) - 1)(x^(n + 1) + 1)/N. N = 1 + x^2 + ••• + x^(2n) > 1 + x^(2n), since x is an integer, and because 2n > n + 1, 1 + x^(2n) > 1 + x^(n + 1) > x^(n + 1) - 1. Therefore, N > x^(n + 1) + Therefore, N does not divide x^(n + 1), and therefore, N is not prime. Q. E. D. Notice how x can be any positive integer base larger than 1, and this would hold true.
@@angelmendez-rivera351 Thanks for describing a general case. The result is the same no matter what numeral system you use. They all have one essence :)
Math expert said" Here is the deal"...Rabbit said" Ok show the carrot"
Lol
It’s all about the base! 😂
How did u find this video?
Dr Peyam
Oh nvm, I forgot I sent it to you lol
wow a comment from the past, welcome to the future bro
How can that happen?
A comment from the past?? 🥶
All bout that base, bout that base, no factors!
Someone response "haaaalllooww" 0:04
Yes!
@@blackpenredpen haha who was that?
InDstructR It was shao tu tu :D (sorry for spelling I’m not familiar with pin-yin anymore)
I love how you can prove something complicated like this.
Alternative and quicker proof:
We know that (1+x+...+x^n) is a factor of (1+x^2+x^4+...+x^2n) for n > 1(you can check this easily since the n+1-th unit root is a zero of both), so we are also finished for x=10.
It can be quicker proof if you leave too many details.
Similarly you could state 1+10^2+10^4=(10^(2n)+1)/99, then (10^n-1)*(10^n+1)/N = 99, is not possible because 10^n+1 < N.
Is it similarly short?
details is much deeper. for example, to someone that (n+1)-th unit root is root of (1+x+...+x^n) is not obvious. You need here either again geometric sum formula, because you can't sum complex numbers easily. so you'll get (x^(n+1)-1)/(x-1) and you need to fill in alpha here: (e^i(n+1)(2pi/(n+1))-1)/(e^i(2pi/(n+1))-1) = (e^i(2pi)-1) = 0/something = 0. Either use geometric approach, then you need to know that you're going to sum vectors from center to equaly spaced n-gon. Either handwavy say that ngon center of mass is in it's center, so sum of vectors is zero. Or state that all vectors has same length, and angle between them same as angle between sides of ngon, so using triangle rule of vector summation you can construct ngon with unit side, whose sides are vectors we gonna sum, and sum of its sides will go back to starting point of summation, which means that sum is zero. Anyway, it's just not obvious. I would like to know if you have an easier proof.
Next, when you have one root of (1+x+...x^n), I don't see how you can tell that if two polinomial share root, then one of them is factor of other. I guess you claim that (1+x+...+x^n) share all the factors with (1+x^2+x^4...+x^2n). Then, we should either prove somehow indirectly, or say what roots exactly (1+x+...+x^n) has. From proof with (x^(n+1)-1)/(x-1) and e^i(2pi/(n+1)) we can show that e^i(2pik(n+1)) also works. But we didn't yet checked (1+x^2+x^4..+x^2n). Lets actually check. (x^(2n+2)-1)/(x^2-1) -> (e^i(2n+2)(2pik/(n+1))-1)/something. exponent is e^i(4pik), so it is indeed 0/something. But, here where it comes :D this *something* is e^i2(2pik/(n+1))-1. It can be zero! You can't divide by zero. When it zero? when 2*k/(n+1) is whole number. So n+1 has to be even, and also we know that k < n+1, so the only way it may happen is k = (n+1)/2. And, for even n it is possible. So, we need to find out what is 1+x^2+x^4...x^2n when x = e^i(2pi*((n+1)/2)/(n+1)) = e^i(2pi/2) = e^i(pi) = -1. so, it becomes 1+(-1)^2+(-1)^4...+(-1)^2n = n+1.
So, nope, it doesn't share all roots when n is odd. and, you may verify that 1+100+10000 is not divisible by 1+10+100.
As on very cool site is stated: there is always very short, nice and wrong solution.
@@r75shell Given the history of his Last Theorem: perhaps we should term this "The Fermat Trap".
😉
@@r75shell 1+100+10000 is divisible by 1+10+100, but 1+100+10000+1000000 is not divisible by 1+10+100+1000, which is probably what you meant to write.
@@jcsahnwaldt 10101 is not divisible by 111
111 times 91 is 10101.
Try this one in next video:
f(x)=ax^2+bx+c. Where a#0
And f(f(1))=f(f(2))=f(f(3))
Find a,b,c
Even After buying a best microphone ...he stil having the habit of holding something like microphone .
What a beautiful proof. I love it. You should do more number theory like this. Great !
Great lockdown beard :P
See his beard in his latest videos.
Alternatively you can note that if N is prime then 99 = (kN (10^(n+1) +/- 1) ) / N for some positive integer k. Thus 99 = k(10^(n+1) +/- 1). But the only solution to that equation with positive k and n is k=1 and n=1 and N=101.
He loves the giant mic so much that he had to hold something comparable.
Great shirt and great video! :)
Amazing!!! How do you have these ideas? Is so good! Thank you!
11:45 “YES VERY IMPRESSED!” lol
I love youre videos from France !
Did anyone else think a) he was writing binary notation and b) the bunny was the mic?
I am impressed too, nice work
Thanks!
You recalled my memories of MR. BEAN today thanks
You are amazing man
So cool idea!
I thaught it's in binary. ... perhaps I was going to say goodbye RSA😂😂😂
Dgsn Dmt It's still true in binary. It's true in all bases.
Nice to see a brpr video on my birthday!
Hi love the videos
Good job 👍
my favourite channel!
Nice Proof, i enjoyed this video
Thank you sir 😁
Well done
*Love from 🇮🇳India(भारत)*
Once we have N = (10^(n+1) + 1)(10^(n+1) - 1) / 99 we can immediately observe that, for n > 1, both factors are greater than 99 so we must have some non-trivial factorisation and N cannot be prime.
Very good new friend, what a good math Bunny
Sir please provide more videos on Olympiads,Putnam, number theory problem
you are a legend
Took me like 3 minutes to realize it wasn't binary, lmao
Proof works if it is binary, just need to check the single special case (101 in binary = 5 in decimal) and the proof works everywhere else.
Mind blown 🤯
brilliant!
4:46 *When the teacher erases the board before you're done copying*
When the viewer forgets they can pause a video (unlike a lecturer in RL)
Nice ending. That’s clever.
I came up with a completely different representation of the series:
. . . x
f(x) = ∑ 100^n
. . n=0
isnt that what he did too? expanding yours we get 1 + 100 + 100^2 ... + 100^x
and in his we get the same
Vivek Panchagnula Exactly. This is not a new representation, this is literally what was presented in the video.
大家好，我来给大家介绍一下，这是我的新朋友，小兔兔！
I'm a simple man.
this problem should be reused on some maths olympiad in 2025. "In base 2025, when is the expression 1111111....111111111111 a prime?"
Superb
Cool dude 😍😍
In fact, if you instead look at (10^n-1)*(10^n+1)/99 = N, you'll get factorization straight ahead.
if n is even, then first one is obviously divisible by 99. (just look at decimal representation)
and if n is odd, then first is divisible by 9 (decimal representation) and second is divisible by 11, which is not so obvious, but provable by divisibility by 11 criteria, or using modular arithmetic you have -1^(odd power) + 1 = 0.
When I saw 101010101 and the bunny I thought oh cool its in bunnary.
that plot twist at the end tho
I am impressed too
0:33 LOL
very elegant
I don’t understand but I still support you
Hi Steve sir
😄. ❤ from 🇮🇳
Thanks!
Sir's real name is steve
Do you take requests math for fun? I never saw anyone integrate step functions. For example is there a form for integrating y=[x] or y=[x^2] (step functions)?
I did that on already czcams.com/video/Sz3vBh7nBTE/video.html
@@blackpenredpen
Without looking at your solution, my intuition would be to break proper integrals of step functions into series, with each term being one step, which becomes the trivial integral of a constant across the range.
Now l look at the link to see if I came close... and to see if you offer a solution to the improper integral of a step function, where I have no idea how to even start... :(
I just happened to do this in diff eq, not hard if u take the laplace and then inverse laplace of the function
Will you make such a video for number with others base? By first look i thought it is about number in binary system
Дмитро Шум This works in any base.
I say, that bunny is a good listener!
I have a question
So...the best friend is only for 0
Almost, you can't use x=1 (but in this case, the sum just evaluates to n).
(Also, if we drop thinking about evaluating the series, we can use the relation (1-x)(1+x+x^2+...)=1 in a formal setting)
This theorem holds true in any positive integer base, except for base 1. This is because if 2n > n + 1, then x^(2n) > x^(n + 1) if x > 1, and for all integer x > 1, x^2 - 1 is a positive integer, which means (x^(n + 1) - 1)(x^(n + 1) + 1)/N is a positive integer. This all means N cannot divide x^(n + 1) + 1 regardless of what x is, so long as it satisfies the stated conditions. So N would not be prime regardless of the base.
I am impressed
This proof applies to any base. Only 101 can be a prime number, but is not always. Finding an explicit prime factor is also possible. If the number of ones itself is not a prime it is trivial. 10101010101 is divisible by 101 and 10101. So six ones can be divided by the same formed number with a factor of the number of ones. If the number of ones is prime or odd for that matter you can divide it by a number made of just ones. So 111 | 10101, 11111 | 101010101 and so. Again this is true in any number base.
now to prove that (1+10+...+10^(odd x)) divides (1+100+...+100^(same x)) for every base
Divisibility tricks incoming!
Well done my friend. You may also prove this in an "explicit" way, like in the rap songs (finding 2 factors). If you have an even number of ones (N), for example lets say 8 (101010101010101) you may find at least 2 factors: 1010101 and 100000001 (10^8+1). This is evident, and easy to prove. If N is odd the problem is more difficult but you may also proove that e.g. 11111*9091=101010101 ; 1111111*909091=1010101010101 ; and this goes on to infinity (add 11... x 90... =1010...). The prove this is true is not very difficult (but it does not fit in here).
Yes, I am impressed. Nice problem. And it works for every base, not only 10. This is awesome so many numbers are ruled out.
Good luck and work
"Namaste" sir from india 🤩🤩
I want to ask blackpenredpen that does he do the problem before uploading the video or he does it for first time in the video only pls reply bprp.........🤔🤔🤔🤔🤔😄😄😄😄
He solves it before the video or reads it somewhere else. I dont believe someone would do it this fluent. Not even BPRP.
@@disco.jellyfish let bprp reply himself
@@disco.jellyfish the way he explains it seems like he is solving on the spot
He does it before filming. When I was a teaching assistant in calculus I the first time I tried demonstrating a problem from the book in class from scratch. It required a clever step that did not immediately occur to me and I looked like an idiot. I suspect BPRP has had the same experience.
I think it isn´t possible since it would be time consuming. I guess he practices it before uploading, but he´s really capable.
so I started with this, just to have a feel of the numbers:
g = 0
for i in range(0, 8):
g = g+2**(2*i)
print(i, g)
which resulted in:
0 1
1 5
2 21
3 85
4 341
5 1365
6 5461
7 21845
Only to find out that the problem is not in binary. The damn bunny got me this time ...
I like what you do
Neat!
*i am impressed*
When we get the closed formula we can end up with Zsigmondy theorem saying that numerator will gain new prime divisors. Q.E.D.
I know why you took that bunny bprp because you are used to hold something in your hand and the only difference is that previously you have taken a spherical mike and now as you have a short and tiny Mike on your shirt , am I right ?
The statement at 6:40 - why do we know that N is prime if it divides one of the factors in the numerator?
He's saying IF N is prime [for proof by contradiction]. IF then statement.
IF N is prime (and given that n is an integer greater than 1 {implying (10^(n+1) - 1) and (10^(n+1) +1)) are integers}, then either (10^(n+1) - 1)/N is an integer
or
(10^(n+1) + 1)/N is an integer.
since that whole fraction equals 99 (an integer)
He later contradicts this statement by showing that N > 10^(n+1) + 1 > 10^(n+1) - 1
which means the whole fraction is not an integer.
99 = non integer is a contradiction
Thus, his original statement that N is not prime given n > 1 is true.
The two numbers 10^(n+1)+1 and 10^(n+1)-1 have no common factors because they are odd and differ only by 2. That means in particular they don't have a common prime factor. Therefore N, being a prime by assumption, must either divide the one or the other. That can't be because N is bigger then either factor. So N cant't be a prime to begin with.
That is a classic argument in many number-theoretic proofs.
Kurt Meier Because that is one of the definitions of a prime number set as the ideal of the group of natural numbers. If p is prime, then if p divides the product ab, then it divides a, or it divides b. Alternatively, when not used as a definition, it is a theorem in number theory.
@@angelmendez-rivera351 thank you for your answer.
@@Bayerwaldler thank you for your answer.
You sure youre taking the lockdown well?
He obvs is taking the lockdown well, by relying on the capable support of the cuddly toy.
You know, from 99=(10^(n+1)-1)(10^(n-1)+1)/N and N|10^(n+1)-1 or N|10^(n+1)+1, we get 99=k(10^(n+1)+1) or 99=(10^(n+1)-1)k with k>=1 (natural number), so 99>=10^(n+1)-1, i.e. 100>=10^(n+1), hence n
Iikes for the bunny!♥️
Love from Bangladesh
Have comments been displaced on yt?
After showing that N = ((10^2n)-1)/99 it is easy to see that the number takes the form 99999999...99/99 with an even number of 9s, because it is one less than 1000000000...00 with an even number of zeros. On the numerator the number can be written as 99 (100)^n + 99 (100)^n-1 +...+ 99 so, factorizing 99, it is divisible by 99.
António Monteiro The numerator is obviously divisible by 99 because N is the quotient, and this quotient is a natural number. This does not prove N is prime, it only proves N is a natural number, which we already knew.
Man i have a problem to you:
Show that every single number has a multiple which can be written only using the digits 1 and 0.
it's not true, the digit 9 has no number K so that 9K is of this form. To see this note that 9=10 -1 so we would require 10K-K to be of this form. e.g. if k is 2 digits a1 a2 then we need a1 a2 0 - a1 a2 to give a three digit andswer d1 d2 d3 where all the d's are 1 or 0. d3=0 - a2
so a2=0 or a2 = 9 ... i haven't clarrified the details but it's probably possible to arrive at a contradiction
unless trivially you allow 9 * 0 as a solution
@@richardfredlund3802 what about 101010101010101010, 110011001100111 and 11111111100?
Richard Fredlund Your statement doesn't actually prove anything. In fact, what you stated is incorrect.
jordan peretti Yes, those are divisible by 9. If the number of 1s in the decimal expansion is a multiple of 9, then the number is a multiple of 9.
So beautiful proof...
Is this true for any sum of numbers raised to the fourth power?
Before watching, my guess is only when number of digits is 6k-3, kEN (same if its a binary number).
Nice mic!
I thought the bunny was the duster
It is interesting to look at this in other number bases.
For example, 101 is prime in binary and hex as well as in decimal,, but not in octal where it factors into 5 and octal 15.
However your argument for n>1 works in any base, so octal has no primes of that form at all.
So my next question is exactly which bases are like octal and have no "one-oh" primes at all? Is there a pattern to explain why octal is different?
True River As I said elsewhere, the problem can be simplified as simply solving the equation n^2 + 1 = p for natural n > 1, where p is a prime number. Note that if p = 2, then there are no solutions, so you can focus only on the odd primes. It may be possible to show that you may only need to focus on Gaussian primes.
If n > 1 and n = 2m + 1 for some integer m, then n^2 + 1 is divisible by 2, and therefore, not prime. This is a trivial case, so the more interesting question is, what are the *even* bases such that 101 written in that base is not prime? In other words, what are the *even* numbers n such that n^2 + 1 = p, where p is prime? This question can in turn, be translated simply as, which natural numbers m do *not* satisfy the equation 4m^2 + 1 = p? m = 4 and m = 6 are the first two numbers that do not satisfy the equation, a.k.a the first two anti-solutions.
4m^2 + 1 is congruent to 1 modulo 10, 5 modulo 10, or 7 modulo 10. Since any natural number which is congruent to 5 mod 10 is not prime, except for 5 itself, it follows that almost all anti-solutions to the equation of 4m^2 + 1 = p are given by m such that 4m^2 + 1 == 5 (mod 10), which implies 4m^2 == 4 (mod 10). m^2 is congruent to 0 modulo 10, 1 modulo 10, 4 modulo 10, 5 modulo 10, 6 modulo 10, or 9 modulo 10.
If m^2 == 0 (mod 10), then 4m^2 == 0 (mod 10).
If m^2 == 1 (mod 10), then 4m^2 == 4 (mod 10).
If m^2 == 4 (mod 10), then 4m^2 == 6 (mod 10).
If m^2 == 5 (mod 10), then 4m^2 == 0 (mod 10).
If m^2 == 6 (mod 10), then 4m^2 == 4 (mod 10).
If m^2 == 9 (mod 10), then 4m^2 == 6 (mod 10).
Therefore, almost all the anti-solutions are given by m such that m^2 == 1 (mod 10), or m^2 == 6 (mod 10). Therefore, almost all the anti-solutions are given m == 1, 4, 6, 9 (mod 10).
EDIT: The above implies that some of the even bases for which 101 is not prime are those which are congruent to 2 modulo 10, or 8 modulo 10, which includes octal. The only exception is binary, because 2^2 + 1 = 5, which is the only prime number that is congruent to 0 modulo 5. This implies that the only possible candidates for bases in which 101 *is* prime are those which are congruent to 0 modulo 10, 4 modulo 10, or 6 modulo 10, and otherwise, binary is the only such base.
EDIT 2: Notice that I said candidates, because some bases which are congruent to 0 modulo 10, 4 modulo 10, or 6 modulo 10 still do result in 101 not being prime, although these bases are the exception. This is because, while every prime of the form 4m^2 + 1 is congruent to 1 modulo 10 or 7 modulo 10, not all numbers of this form and congruency classes are prime. I think an argument can be made that almost all of them are, but there are is at least a nonzero finite number of exceptions.
@blackpenredpen I challenge you to solve this same question treating these numbers as binary numbers!! 🤩🤩
BPRP needs a bigger whiteboard.
This is just temporary : )
After getting of 99N=(...)(...) you can say that if n>1 then each of brackets is greater than 99 so each of brackets if less than N.
Гера Татаринов But this is not true. The bracketed quantities are not less than 99 if n > 1.
@@angelmendez-rivera351 it's my mistache, words less and greater should be changed
Here is another proof. Let n be the number of 1's in N. If n is even and n>2 then obviously N can be divided by 101. If n is odd, then N can be divided by 111111...1 (n digits). In fact N = 909090...91 * 111111...1. Therefore, 101 is the only prime in this form.
What about doing it in binary :)
Николай Шерстюк The result is identical in binary. In fact, this works for any standard base. The proof is identical, except you just replace 100 with another base, since the proof never relied on the fact that the base is 100, it merely relied on the properties of inequalities and factorization on a polynomic level.
You mean instead of bunnary?
The rabbit seems unimpressed.
Honestly it was too easy for her. So yea....
When a rabbit is more smarter than me?
You (😑+🐰)do great team....👍👍👍
It's a beautiful problem, but I have two similar question for you. I think they are not too easy to solve.
Are there infinite prime numbers in form of 10^(2^n)+1? (n is a positive integer)
Are there infinite prime numbers in form of (10^p - 1)/9? (p is a prime number)
in consecutive order:
yes, no.
my working is too messy and im too tired to post it.
Mr. Bean nostalgia !!
Wouldn't it be cool if you could push a button at the right moment, and the bunny said, "Oooooh"
William Vollrath that will be so awesome!
I've got an different solution from a point if N is prime on 99=[(10^(n+1)-1)(10^/n+1)]/N N must be one of the two terms,there is two possibilities here, if N is the term 1,the 2nd term would be 99 and N would be 98(not prime);the second possibility is N being term 2 in this situation N would be 100(not prime,too) also we cant get 98 and 100 in our main equation N=1+100+100^2+...