My Math Forum Can any teach me how do find a number is prime or not??
 User Name Remember Me? Password

 Number Theory Number Theory Math Forum

 October 14th, 2012, 10:54 AM #1 Member   Joined: Sep 2012 Posts: 69 Thanks: 0 Can any teach me how do find a number is prime or not?? I know there is a method to find a number is prime or not!! Can anyone teach me how to find it by using fermat's little theorem with a specific example!! Also I saw a method that says a number n is prime if the number n and $\sqrt{n}$ has no common divisor!!??!! can anyone explain this too?? thanks
October 14th, 2012, 01:11 PM   #2
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Can any teach me how do find a number is prime or not??

Quote:
 Originally Posted by eChung00 Also I saw a method that says a number n is prime if the number n and $\sqrt{n}$ has no common divisor!!??!!
False.

 October 14th, 2012, 06:21 PM #3 Senior Member   Joined: Aug 2012 Posts: 2,209 Thanks: 650 Re: Can any teach me how do find a number is prime or not?? The standard method is by trial divisors. Given a number, you divide it by all the primes less than it; and if none of them divides your number evenly, then your number is prime. A performance optimization is that it's sufficient to divide by the primes less than or equal to the square root of your original number. Perhaps that's where you heard of the relationship to sqrt(n). As you stated it, it doesn't make too much sense: because if n is prime, then sqrt(n) is irrational and not an integer. For large values of n, the trial divisors method is very slow computationally. That's when a lot of advanced tricks and techniques are used. There's a large literature on the subject. The Wikipedia article is a good starting point. http://en.wikipedia.org/wiki/Primality_test
October 14th, 2012, 07:52 PM   #4
Member

Joined: Sep 2012

Posts: 69
Thanks: 0

Re: Can any teach me how do find a number is prime or not??

Quote:
 Originally Posted by Maschke The standard method is by trial divisors. Given a number, you divide it by all the primes less than it; and if none of them divides your number evenly, then your number is prime. A performance optimization is that it's sufficient to divide by the primes less than or equal to the square root of your original number. Perhaps that's where you heard of the relationship to sqrt(n). As you stated it, it doesn't make too much sense: because if n is prime, then sqrt(n) is irrational and not an integer. For large values of n, the trial divisors method is very slow computationally. That's when a lot of advanced tricks and techniques are used. There's a large literature on the subject. The Wikipedia article is a good starting point. http://en.wikipedia.org/wiki/Primality_test

so you saying that I cannot use fermat's little theorem wont help on deciding a number is prime or not??

October 14th, 2012, 11:15 PM   #5
Senior Member

Joined: Aug 2012

Posts: 2,209
Thanks: 650

Re: Can any teach me how do find a number is prime or not??

Quote:
 Originally Posted by eChung00 so you saying that I cannot use fermat's little theorem wont help on deciding a number is prime or not??
Interestingly, that doesn't work. Fermat's little theorem tells you that if a number is prime, it satisfies such and so. But the converse may be false. That is, there are numbers n such that a^(n-1) = 1 (mod n) for all a relatively prime to n; yet, n is not prime. These counterexamples to the converse of Fermat's little theorem are called Carmichael numbers.

http://en.wikipedia.org/wiki/Carmichael_number

So you can use Fermat's little theorem to prove a number is not prime; but you can't use it to prove a number is prime.

October 15th, 2012, 04:30 AM   #6
Math Team

Joined: Mar 2012
From: India, West Bengal

Posts: 3,871
Thanks: 86

Math Focus: Number Theory
Re: Can any teach me how do find a number is prime or not??

Quote:
 Originally Posted by eChung00 Can anyone teach me how to find it by using fermat's little theorem with a specific example!!
Fermat's little theorem is not so helpful in general. Though it may be an efficient probabilistic test, it may take several tests for certify a number a prime.

See, Fermat's Primality Test

October 15th, 2012, 05:40 AM   #7
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Can any teach me how do find a number is prime or not??

Quote:
 Originally Posted by mathbalarka Fermat's little theorem is not so helpful in general. Though it may be an efficient probabilistic test, it may take several tests for certify a number a prime.
Au contraire; for randomly-selected large primes or composites, it is almost certain to give the correct answer in one attempt and is essentially the fastest method known. (Small primes and composites are easily handled with other methods.)

 October 15th, 2012, 12:00 PM #8 Member   Joined: Sep 2012 Posts: 69 Thanks: 0 Re: Can any teach me how do find a number is prime or not?? thanks to all!!!!!!!!!!

 Tags find, number, prime, teach

### When is Fermat's little theorem taught in india

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post nukem4111 Number Theory 4 October 7th, 2013 11:29 AM matqkks Academic Guidance 1 July 7th, 2013 09:56 PM xfaisalx Number Theory 15 July 6th, 2010 03:32 AM dancer42 Number Theory 5 March 18th, 2008 02:42 PM matqkks Number Theory 0 December 31st, 1969 04:00 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top