My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
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
eChung00 is offline  
 
October 14th, 2012, 01:11 PM   #2
Global Moderator
 
CRGreathouse's Avatar
 
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 has no common divisor!!??!!
False.
CRGreathouse is offline  
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
Maschke is offline  
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??
eChung00 is offline  
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.
Maschke is offline  
October 15th, 2012, 04:30 AM   #6
Math Team
 
mathbalarka's Avatar
 
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
mathbalarka is offline  
October 15th, 2012, 05:40 AM   #7
Global Moderator
 
CRGreathouse's Avatar
 
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.)
CRGreathouse is offline  
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!!!!!!!!!!
eChung00 is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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





Copyright © 2019 My Math Forum. All rights reserved.