Proof about primes and gcd

In summary, in order to prove the statement "p is prime iff for any integer a, either (a,p)=1 or p divides a," we can use a proof by contradiction. By assuming that p is not prime and showing that this leads to a contradiction for all possible (a,p) pairs, we can conclude that the original assumption was false and therefore p must be prime. Using specific examples to prove this statement is not enough, as it only shows that the statement is true for that specific example, but not for all cases.
  • #1
AlexChandler
283
0

Homework Statement



prove that p is prime iff for any integer "a" either (a,p)=1 or p divides a

(where (a,p) denotes the gcd of a and p)

Homework Equations



(a,b)= the greatest common factor of a and b

The Attempt at a Solution



I had no trouble with proving the forward direction of the statement. But for the backward direction, here is what I have:

for any integer "a", let either (a,p)=1 or p divide a
Now assume that p is not prime.
The following must hold true:
either (6,4)=1 or 4 divides 6
Since both of these statements are false, this is a contradiction.
Therefore p must be prime.
Q.E.D.

It seems okay to me to use an example at this point to arrive at the contradiction. Is this a legitimate way to prove the theorem?
 
Physics news on Phys.org
  • #2
AlexChandler said:
It seems okay to me to use an example at this point to arrive at the contradiction. Is this a legitimate way to prove the theorem?

No. You want to show this works for all (a,p). You're on the right track wanting to show by contradiction, but try this instead:

Case 1: Let (a,p) = 1, p does not divide a and assume to contrary that p is not prime. So p = xy, x,y > 1. How can we get a contradiction?

Case 2: Let (a,p) != 1, p divide a and assume to contrary that p is not prime. So p = xy, x,y > 1. How can we get a contradiction?
 
  • #3
Ok thank you. That seems a much better way to prove this. However, I am still not seeing the logical flaw in the argument I used. If you let "(a,p)=1 or p divide a", and assume that p is not prime, isn't an example of a contradiction enough to conclude that the assumption was false?
 
  • #4
I see what you're talking about now.

This unfortunately won't work. You've shown that you obtain a contradiction only for that example (which is good). However, assuming that we did it your way, how do we know that there don't exist examples where there's not a contradiction and the example satisfies all three statements?

By keeping things general, you'll be able to show that you'll obtain a contradiction for every time you choose p to not be prime.
 
  • #5
AlexChandler said:
Ok thank you. That seems a much better way to prove this. However, I am still not seeing the logical flaw in the argument I used. If you let "(a,p)=1 or p divide a", and assume that p is not prime, isn't an example of a contradiction enough to conclude that the assumption was false?

I think this only works when you're making a statement about all non-primes having those properties. That is, your counterexample must be against a statement that says "for all non-prime p, (a,p)=1 or p divides a". However, in your statement, you're only assuming that there might exist one such p that isn't prime with those properties, and so a counter example would not show that the statement is wrong (just that the p you chose doesn't fit the description; there are still infinitely many p to choose from that aren't prime that might fit your requirements).

Against a "for all" statement, such as for all [itex]f[/itex] that are continuous at any number of points, [itex]f[/itex] is differentiable at those points, you can provide a counter example ([itex]f(x) = |x|[/itex] works here) and that takes care of the problem.
However, for a "there exists" statement, such as "[itex]\exists \delta \; s.t.\; \forall \varepsilon > 0, |x-x_0| < \delta \implies |f(x)-L|<\varepsilon[/itex]
If you just pick [itex]\delta = 100[/itex], it probably wouldn't work for the implication, but would that disprove that limit, or would there still be a possibility that [itex]\delta = 99[/itex] would work? If not, would 98? 97? etc
 

1. What is the proof for the infinitude of prime numbers?

The proof for the infinitude of prime numbers was first discovered by the ancient Greek mathematician Euclid. It states that there are infinitely many prime numbers, and it is commonly known as Euclid's proof. The proof goes as follows: Assume there is a largest prime number, call it p. Then, we can form a new number q by multiplying all prime numbers from 2 to p and adding 1. This new number q is either prime itself (which means our assumption that p is the largest prime number is wrong) or it has a prime factor that is not on our list (which again contradicts our assumption). Therefore, our assumption is wrong and there is no largest prime number, proving the infinitude of primes.

2. What is the proof for the fundamental theorem of arithmetic?

The fundamental theorem of arithmetic states that every positive integer can be uniquely represented as a product of primes. The proof for this theorem is based on the fact that every integer can be factored into a unique combination of prime numbers. This is also known as the unique factorization theorem. The proof involves using the Euclidean algorithm and induction to show that every integer has a unique prime factorization.

3. How is the greatest common divisor (GCD) of two numbers related to prime numbers?

The greatest common divisor (GCD) of two numbers is the largest positive integer that divides both numbers without leaving a remainder. The GCD is related to prime numbers because it is the product of all common prime factors of the two numbers. For example, if the GCD of two numbers is 12, it means that the two numbers have at least one common prime factor of 2, and possibly other common prime factors as well.

4. Can prime numbers be used to efficiently find the GCD of two numbers?

Yes, prime numbers can be used to efficiently find the GCD of two numbers using the Euclidean algorithm. This algorithm involves repeatedly dividing the larger number by the smaller number until the remainder is 0. The last non-zero remainder is the GCD of the two numbers. This algorithm is based on the fact that the GCD of two numbers is the same as the GCD of the smaller number and the remainder of the larger number divided by the smaller number. By using prime numbers as factors, the algorithm can be optimized and the GCD can be found in fewer steps.

5. Are there any other applications of prime numbers and GCD in mathematics?

Yes, prime numbers and GCD have many applications in mathematics, including cryptography, number theory, and algorithms. Prime numbers are used in encryption methods to ensure the security of data, as well as in generating random numbers. GCD is used in the Euclidean algorithm, which has applications in finding modular inverses and solving linear Diophantine equations. In addition, prime numbers and GCD have connections to other mathematical concepts such as the Chinese remainder theorem and Euler's totient function.

Similar threads

  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
12
Views
985
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
919
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
24
Views
615
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
Back
Top