# Thread: Using the fact that a pair of numbers is relatively prime to prove that one is prime

1. ## Using the fact that a pair of numbers is relatively prime to prove that one is prime

The GCD(30030, 257) = 1
Using that fact, and the prime factorization of 30030 = 2 * 3 * 5 * 7 * 11 * 13
How can I show that 257 is prime.

I'm not sure this is true, but is it because all non-prime numbers have a prime factorization, and since 30030 and 257 are relatively prime (only have a common divisor of 1) and the the next lowest prime is 17 and since 17 != 257 and 17 * 17 = 289 and 289 > 257, we know that 257 is prime?

2. ## Re: Using the fact that a pair of numbers is relatively prime to prove that one is pr

Originally Posted by Celcius
The GCD(30030, 257) = 1
Using that fact, and the prime factorization of 30030 = 2 * 3 * 5 * 7 * 11 * 13
How can I show that 257 is prime.

I'm not sure this is true, but is it because all non-prime numbers have a prime factorization, and since 30030 and 257 are relatively prime (only have a common divisor of 1) and the the next lowest prime is 17 and since 17 != 257 and 17 * 17 = 289 and 289 > 257, we know that 257 is prime?
You have given a virtually complete proof. To make the argument absolutely clear, you should perhaps state explicitly that if a number is not prime, then at least one of its prime divisors must be less than (or equal to) its square root.