See this proof:
Anyone else has a better solution?
I tried Wilson's Theorem, but it's still too lengthy and full of arithmetic calculation.
I tried Miller-Rabin Test, but to prove is another prime is another daunting task.
I tried Pocklington primality test, but there's still plenty of calculations to work on.
Help!
Easy Math Editor
This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.
When posting on Brilliant:
*italics*
or_italics_
**bold**
or__bold__
paragraph 1
paragraph 2
[example link](https://brilliant.org)
> This is a quote
\(
...\)
or\[
...\]
to ensure proper formatting.2 \times 3
2^{34}
a_{i-1}
\frac{2}{3}
\sqrt{2}
\sum_{i=1}^3
\sin \theta
\boxed{123}
Comments
Sort by:
Top NewestI may seem a bit dumb here, but isn't a prime number a number which isn't divisible by any numbers but 1 and itself?
Log in to reply
Sieve of Eratosthenes is the fastest way, but not the elegant way I think.
Log in to reply
I don't suppose you want a Computer Code , do you sis ?
Log in to reply
83 is a prime number because it is not divisible by 2, 3, 5, 7 and is less than 10^2. That takes just 5 operations to show.
Why are you looking for something else?
Log in to reply
It might be unrelated , but do you know of Bertrand Russell and Alfred North Whitehead who wrote a 360 page proof for proving something as obvious as 1+1=2 ?
Log in to reply
I've heard of that one. Do you have a link to it?
Anyhow, which part of my proof is not valid?
Log in to reply
article which I read just over a week ago .
I don't have the link to the proof , but here's the link to theThere's nothing wrong in your proof , since we just have to check that there's no number less than 83 that's a factor of 83.
But I think @Pi Han Goh wants to prove that 83 is prime using some other proof , I guess so .
Log in to reply
I think that maybe he wanted a proof based on mathematical logic for the primality of 83 and not a computational one (albeit computational methods are the most efficient for small values). Maybe he's considering a general solution to test the primality of a number n in the most efficient and logical way possible that does not rely on heavy computations. Maybe he considered n=83 to get the ball rolling.
I think I used too many "maybe"s in a single comment. :P
Log in to reply
I think it should be a "she" instead of "he" .
Log in to reply
@Pi Han Goh is female? :o
What the *$#@??Log in to reply
MAIL
Log in to reply
LAIM. :3
But your comment soundsLog in to reply
Log in to reply
Log in to reply
Log in to reply
Log in to reply
Log in to reply
Maybe....
Log in to reply
⌣¨
Log in to reply
Log in to reply
Why mot try AKS?
Log in to reply
Log in to reply
primality test on this planet and two others
The bestLog in to reply
Log in to reply
a as possible [because there are infinitely many numbers coprime to a given prime] to ensure that the number taken is prime and we also have to keep x as a free variable, so the computation requires extensive use of binomial theorem when larger numbers are to be tested.
If I remember correctly, that is a deterministic algorithm that requires you to check for as many values ofHow do you expect someone to expand a binomial to the power 83 quickly? Ain't nobody got time for that! :3
A formal mathematical proof is completely different from a computational (computer-assisted) one. Your approach works if someone were to check the primality using a computer program but that doesn't work in pure mathematics. Atleast, that's what I think!
Log in to reply
Why'd you expect to run the algorithm by hand?
Log in to reply
Take the 3n+1 conjecture as an example. Many people have proved the validity of the conjecture for extremely high values of n but it is still an open unsolved problem in mathematics awaiting for a rigorous proof.
Log in to reply
(I do not claim that I know the algorithm fully but there are definitely ϕ(n) such integers less than n and just using the integers less than n suffices to work because you are working in Z/nZ)
I did not claim that the Collatz Conjecture has been proven at all. The purpose of running through high numbers was to check for a counterexample, not prove it.
Computers can be and has been used to create rigorous proofs. Unfortunately, at least 80% of all people outside proffessional mathematics think otherwise.
Log in to reply
Log in to reply
Z/nZ={[0],[1],[2,],…,[n−1]}
where, [k] is an equivalence class in the subgroup Z/nZ, i.e., the elements of the class give a residue of k modulo n.
So, the elements that are considered in the subgroup are not limited to the totatives of n. Now, I haven't yet read the full proof of AKS nor do I understand it properly yet but I'd like to ask if your claim is that the test works for the whole equivalence class just by testing for the smallest non-negative element of that class?
On second thoughts, maybe it does work since we are working with a congruence relation after all.
P.S - My arguments may sound stupid sometimes, don't get offended by that. We aren't fighting over here. We're just expressing our opinions and having a friendly discussion. :)
Log in to reply
It's alright and I apologise for getting excited too.
Log in to reply
Lucas Primality Test too, but then I got stumped when I have yet to prove that 41 is another prime, but even if I had proven that 41 is prime, finding a value of 1<a<83 such that a82≡1(mod83) and a82/q≡1(mod83) will be another painful task. But still not as tough as Sieve of Eratosthenes. Thank you!
Interesting observation, I totally forgot about AKS. I was consideringLog in to reply
Log in to reply
Yes, I'm looking for something else, 5 operations is getting a little tedious, don't you think?
Log in to reply
I saw a video of terance tao on prime numbers . He provided a contradictory proof that there are infinety many primes. The same proof can be applied here too.
Taking 82 decomposing as 41 . 2 and then adding one will provide us with a number which can't be divisible by any other number other than 1 and itself
Log in to reply
I think you have misunderstood Euclid's argument
Multiplying two prime numbers and adding one does not guarantee a prime. Consider 2×7+1
Log in to reply
Log in to reply
Log in to reply
Log in to reply
Log in to reply
Log in to reply
What about Fermat's little theorem?
Log in to reply