Is there a better way to prove that 8383 is a prime number?

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 4141 is another prime is another daunting task.

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

Help!


Note by Pi Han Goh
4 years, 8 months ago

No vote yet
1 vote

  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:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

What about Fermat's little theorem?

Joel Yip - 4 years, 4 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 Staff - 4 years, 8 months ago

Log in to reply

Yes, I'm looking for something else, 55 operations is getting a little tedious, don't you think?

Pi Han Goh - 4 years, 8 months ago

Log in to reply

I think that maybe he wanted a proof based on mathematical logic for the primality of 8383 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 nn in the most efficient and logical way possible that does not rely on heavy computations. Maybe he considered n=83n=83 to get the ball rolling.


I think I used too many "maybe"s in a single comment. :P

Prasun Biswas - 4 years, 8 months ago

Log in to reply

Why mot try AKS?

Agnishom Chattopadhyay Staff - 4 years, 8 months ago

Log in to reply

@Agnishom Chattopadhyay If I remember correctly, that is a deterministic algorithm that requires you to check for as many values of aa 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 xx as a free variable, so the computation requires extensive use of binomial theorem when larger numbers are to be tested.

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

Image 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 - 4 years, 8 months ago

Log in to reply

@Prasun Biswas Interesting observation, I totally forgot about AKS. I was considering Lucas Primality Test too, but then I got stumped when I have yet to prove that 4141 is another prime, but even if I had proven that 4141 is prime, finding a value of 1<a<831<a<83 such that a821(mod83)a^{82} \equiv 1 \pmod {83} and a82/q≢1(mod83) 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 - 4 years, 8 months ago

Log in to reply

@Pi Han Goh I think the simplest thing to do here is trial division because of the small input.

Agnishom Chattopadhyay Staff - 4 years, 8 months ago

Log in to reply

@Prasun Biswas There is no reason to not accept a computer assisted proof as formal/pure. After all, the computer algorithms are proven to be mathematically working.

Why'd you expect to run the algorithm by hand?

Agnishom Chattopadhyay Staff - 4 years, 8 months ago

Log in to reply

@Agnishom Chattopadhyay But it doesn't guarantee the primality. You can be extra sure by testing for several coprime values but you can never formally state that the number is prime without a rigorous proof. And no matter how much you say, a computer has its limits too.

Take the 3n+13n+1 conjecture as an example. Many people have proved the validity of the conjecture for extremely high values of nn but it is still an open unsolved problem in mathematics awaiting for a rigorous proof.

Prasun Biswas - 4 years, 8 months ago

Log in to reply

@Prasun Biswas Excuse me!! The AKS test is 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 ϕ(n) \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 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.

Agnishom Chattopadhyay Staff - 4 years, 8 months ago

Log in to reply

@Agnishom Chattopadhyay Z/nZ={[0],[1],[2,],,[n1]}\mathbb{Z}/n\mathbb{Z}=\{[0],[1],[2,],\ldots,[n-1]\}

where, [k][k] is an equivalence class in the subgroup Z/nZ\mathbb{Z}/n\mathbb{Z}, i.e., the elements of the class give a residue of kk modulo nn.

So, the elements that are considered in the subgroup are not limited to the totatives of nn. 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 - 4 years, 8 months ago

Log in to reply

@Prasun Biswas

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

It's alright and I apologise for getting excited too.

Agnishom Chattopadhyay Staff - 4 years, 8 months ago

Log in to reply

@Agnishom Chattopadhyay No need to get offended. I was merely expressing my opinion.

Prasun Biswas - 4 years, 8 months ago

Log in to reply

@Agnishom Chattopadhyay Sorry, but what is "AKS" ?

A Former Brilliant Member - 4 years, 8 months ago

Log in to reply

@A Former Brilliant Member The best primality test on this planet and two others

Agnishom Chattopadhyay Staff - 4 years, 8 months ago

Log in to reply

@Agnishom Chattopadhyay Thanks dude, I didn't know about it :)

A Former Brilliant Member - 4 years, 8 months ago

Log in to reply

Maybe....

Pi Han Goh - 4 years, 8 months ago

Log in to reply

@Pi Han Goh You look like a dude though. :P

Prasun Biswas - 4 years, 8 months ago

Log in to reply

@Pi Han Goh ¨\ddot\smile

A Former Brilliant Member - 4 years, 8 months ago

Log in to reply

I think it should be a "she" instead of "he" .

A Former Brilliant Member - 4 years, 8 months ago

Log in to reply

@A Former Brilliant Member What the *$#@?? @Pi Han Goh is female? :o

Prasun Biswas - 4 years, 8 months ago

Log in to reply

@Prasun Biswas

MAIL

Pi Han Goh - 4 years, 8 months ago

Log in to reply

@Pi Han Goh But your comment sounds LAIM\large LAIM. :3

Prasun Biswas - 4 years, 8 months ago

Log in to reply

@Prasun Biswas I think you like to irritate people, don't you ? No offence, really :)

A Former Brilliant Member - 4 years, 8 months ago

Log in to reply

@A Former Brilliant Member Well, doesn't my profile pic already answer that question?

Prasun Biswas - 4 years, 8 months ago

Log in to reply

@Prasun Biswas Yeah, should have guessed so :)

A Former Brilliant Member - 4 years, 8 months ago

Log in to reply

@A Former Brilliant Member :P

Prasun Biswas - 4 years, 8 months ago

Log in to reply

@Pi Han Goh "Mail" ????

A Former Brilliant Member - 4 years, 8 months ago

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

U Z - 4 years, 8 months ago

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 2 \times 7 + 1

Agnishom Chattopadhyay Staff - 4 years, 8 months ago

Log in to reply

@Agnishom Chattopadhyay Yes now too I am not understanding it.

U Z - 4 years, 8 months ago

Log in to reply

@U Z Which part are you not able to comprehend >

A Former Brilliant Member - 4 years, 8 months ago

Log in to reply

@Agnishom Chattopadhyay Thanks

U Z - 4 years, 8 months ago

Log in to reply

@U Z Do you know the correct version lf the argument?

Agnishom Chattopadhyay Staff - 4 years, 8 months ago

Log in to reply

@Agnishom Chattopadhyay Nope , I made it incorrect .

U Z - 4 years, 8 months ago

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=21+1=2 ?

A Former Brilliant Member - 4 years, 8 months ago

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?

Agnishom Chattopadhyay Staff - 4 years, 8 months ago

Log in to reply

@Agnishom Chattopadhyay I don't have the link to the proof , but here's the link to the article which I read just over a week ago .

There'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 .

A Former Brilliant Member - 4 years, 8 months ago

Log in to reply

Sieve of Eratosthenes is the fastest way, but not the elegant way I think.

Marc Vince Casimiro - 4 years, 8 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 11 and itself?

Satvik Golechha - 4 years, 8 months ago

Log in to reply

I don't suppose you want a Computer Code , do you sis ?

A Former Brilliant Member - 4 years, 8 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...