
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
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 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:
 
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:
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:
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:
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:
 
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 
Search tags for this page 
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
prime number  nukem4111  Number Theory  4  October 7th, 2013 11:29 AM 
How and what to teach on a first year number theo  matqkks  Academic Guidance  1  July 7th, 2013 09:56 PM 
Prime Number  xfaisalx  Number Theory  15  July 6th, 2010 03:32 AM 
Looking for a certain Prime number  dancer42  Number Theory  5  March 18th, 2008 02:42 PM 
How and what to teach on a first year number theo  matqkks  Number Theory  0  December 31st, 1969 04:00 PM 