See this proof:

# http://cr.yp.to/talks/2003.03.23/slides.pdf

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 \(41\) is another prime is another daunting task.

I tried Pocklington primality test, but there's still plenty of calculations to work on.

Help!

## Comments

Sort by:

TopNewestSieve of Eratosthenes is the fastest way, but not the elegant way I think. – Marc Vince Casimiro · 2 years, 5 months ago

Log in to reply

I 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? – Satvik Golechha · 2 years, 5 months ago

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? – Agnishom Chattopadhyay · 2 years, 5 months ago

Log in to reply

– Pi Han Goh · 2 years, 5 months ago

Yes, I'm looking for something else, \(5\) operations is getting a little tedious, don't you think?Log in to reply

I think I used too many "maybe"s in a single comment. :P – Prasun Biswas · 2 years, 5 months ago

Log in to reply

– Agnishom Chattopadhyay · 2 years, 5 months ago

Why mot try AKS?Log in to reply

How do you expect someone to expand a binomial to the power \(83\) quickly? Ain't nobody got time for that! :3

Image

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! – Prasun Biswas · 2 years, 5 months ago

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 \(a^{82} \equiv 1 \pmod {83} \) and \( a^{ 82/q} \not\equiv 1 \pmod {83} \) will be another painful task. But still not as tough as Sieve of Eratosthenes. Thank you! – Pi Han Goh · 2 years, 5 months ago

Interesting observation, I totally forgot about AKS. I was consideringLog in to reply

– Agnishom Chattopadhyay · 2 years, 5 months ago

I think the simplest thing to do here is trial division because of the small input.Log in to reply

Why'd you expect to run the algorithm by hand? – Agnishom Chattopadhyay · 2 years, 5 months ago

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. – Prasun Biswas · 2 years, 5 months ago

Log in to reply

deterministic, it definitely guarantees primality and has been rigorously proven. You have misunderstood the algorithm.(I do not claim that I know the algorithm fully but there are definitely \( \phi (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

proveit.Computers

can beandhas beenused to create rigorous proofs. Unfortunately, at least 80% of all people outside proffessional mathematics think otherwise. – Agnishom Chattopadhyay · 2 years, 5 months agoLog in to reply

where, \([k]\) is an equivalence class in the subgroup \(\mathbb{Z}/n\mathbb{Z}\), 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. :) – Prasun Biswas · 2 years, 5 months ago

Log in to reply

It's alright and I apologise for getting excited too. – Agnishom Chattopadhyay · 2 years, 5 months ago

Log in to reply

– Prasun Biswas · 2 years, 5 months ago

No need to get offended. I was merely expressing my opinion.Log in to reply

– Azhaghu Roopesh M · 2 years, 5 months ago

Sorry, but what is "AKS" ?Log in to reply

primality test on this planet and two others – Agnishom Chattopadhyay · 2 years, 5 months ago

The bestLog in to reply

– Azhaghu Roopesh M · 2 years, 5 months ago

Thanks dude, I didn't know about it :)Log in to reply

– Pi Han Goh · 2 years, 5 months ago

Maybe....Log in to reply

– Prasun Biswas · 2 years, 5 months ago

You look like a dude though. :PLog in to reply

– Azhaghu Roopesh M · 2 years, 5 months ago

\(\ddot\smile\)Log in to reply

– Azhaghu Roopesh M · 2 years, 5 months ago

I think it should be a "she" instead of "he" .Log in to reply

@Pi Han Goh is female? :o – Prasun Biswas · 2 years, 5 months ago

What the *$#@??Log in to reply

## MAIL

– Pi Han Goh · 2 years, 5 months agoLog in to reply

– Prasun Biswas · 2 years, 5 months ago

But your comment sounds \(\large LAIM\). :3Log in to reply

– Azhaghu Roopesh M · 2 years, 5 months ago

I think you like to irritate people, don't you ? No offence, really :)Log in to reply

– Prasun Biswas · 2 years, 5 months ago

Well, doesn't my profile pic already answer that question?Log in to reply

– Azhaghu Roopesh M · 2 years, 5 months ago

Yeah, should have guessed so :)Log in to reply

– Prasun Biswas · 2 years, 5 months ago

:PLog in to reply

– Azhaghu Roopesh M · 2 years, 5 months ago

"Mail" ????Log in to reply

– Azhaghu Roopesh M · 2 years, 5 months ago

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

Anyhow, which part of my proof is not valid? – Agnishom Chattopadhyay · 2 years, 5 months ago

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 . – Azhaghu Roopesh M · 2 years, 5 months ago

Log in to reply

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 – Megh Choksi · 2 years, 5 months ago

Log in to reply

misunderstood Euclid's argument

I think you haveMultiplying two prime numbers and adding one does not guarantee a prime. Consider \( 2 \times 7 + 1 \) – Agnishom Chattopadhyay · 2 years, 5 months ago

Log in to reply

– Megh Choksi · 2 years, 5 months ago

Yes now too I am not understanding it.Log in to reply

– Azhaghu Roopesh M · 2 years, 5 months ago

Which part are you not able to comprehend >Log in to reply

– Megh Choksi · 2 years, 5 months ago

ThanksLog in to reply

– Agnishom Chattopadhyay · 2 years, 5 months ago

Do you know the correct version lf the argument?Log in to reply

– Megh Choksi · 2 years, 5 months ago

Nope , I made it incorrect .Log in to reply

I don't suppose you want a Computer Code , do you sis ? – Azhaghu Roopesh M · 2 years, 5 months ago

Log in to reply

What about Fermat's little theorem? – Joel Yip · 2 years, 1 month ago

Log in to reply