Question

how to prove 5657 is prime

Answer 1

Divide it by all natural numbers less than \(\sqrt{5657}\) and see that there are no whole number solutions. Easy if you have a computer I guess, but difficult by hand.

Answer 2

i need mathematical proof, i was given this on exam
i just skipped it
i was trying this at the beginning 5656<5657<5658
5656 and 5658 are both composite
but didn't know how to carry the proof

Answer 3

There's nothing invalid about what I said, it constitutes mathematical proof and takes less than a second with a computer. But I understand that's not what you want.

The problem is, what kind of proof are you looking for?

Answer 4

question asks for any mathematical proof

Answer 5

Empty, actually to save a little time you have to divide the prime being tested by all PRIME numbers (2,3,5,7,11, 13, etc).

Answer 6

why do you want to use numbers less that sqrt(5657)

Answer 7

that's way too much of work to test on all smaller primes

Answer 8

this is a hand problem not a machine problem

Answer 9

True, I guess if I were to do it, I'd use a sieve and it would automatically skip out on those, good catch @wolf1728

@xapproachesinfinity The reason you do that is cause the smallest number of numbers a number can be divisible by and not be prime is two, so basically we're testing to see if it can be possibly written as the product of two numbers... (sorry that's all super wordy sounding, I'll just write this)

5657=a*b

So either a=b or a<b, there's no reason to test them all. I'll give an example for trying to see if 9 is prime:

Test 9/2 = not an integer
Test 9/3 = an integer
(let's keep going though)
Test 9/4 = not an integer but notice, that 9/4 < 3 and we already tested all the numbers up to 3, so we're wasting our time by checking numbers larger than the square root of 9... Hopefully this kinda makes sense.

Answer 10

I have no idea how to show this is prime, but I know 'how' to show that it's prime.

Answer 11

i got that !

Answer 12

so how would we save time and get to the right numbers closest to sqrt(5657)

Answer 13

This is impossible on a test, your teacher is looking for something else no doubt in my mind

Answer 14

Does anything on here look like something you've seen before? Lucas primality test? (never heard of this before so I don't know) https://en.wikipedia.org/wiki/Primality_test#Number-theoretic_methods

Answer 15

i have no idea, he stated show by any mathematical method

Answer 16

no ihaven't studied number theory

Answer 17

What class is this? Are you supposed to prove that it's prime or just show an algorithm that could prove that it's prime?

Answer 18

ya id do the same thing check all primes under sqrt5657

Answer 19

primes under 75 thats not too bad

Answer 20

ill think if there is some neat way to show prime without checking hmm

Answer 21

u know the inverted circle stuff?

Answer 22

hmm the prof left he didn't explain everything hahha

Answer 23

if we can show this number is part of some sequence where only primes are being generated

Answer 24

okay well this inverted circle thing i found on youtube about how the radiuses of these circles in a particular geometry all had prime denominators

Answer 25

hmm i see

Answer 26

something like that maybe.. lets see if we can think of some seuqnece that we can prove must only contain primes and that this prime is in it

Answer 27

we can prove if a number is not prime from fermats little theorem how aobut that

Answer 28

Calculate 2^(n-1) mod n.
If you don't get 1 mod n, then n is not prime.

Answer 29

oh yeah sound much better care to show it please

Answer 30

okay so after finding what 2^(n-1) is you would do the chinese remainder theorem to see the GCD

Answer 31

and ull end up with GCD = 1

Answer 32

and why its working, ud have to understand fermats little theorem

Answer 33

ok

Answer 34

https://www.youtube.com/watch?v=w0ZQvZLx2KA

Answer 35

seems a straight forward theorem