There are some positive integers n that may be written as n=ab for a>1, b>1, and gcd(a,b)=1. There are others that may not be. For instance, 56=8*7 and (7,8)=1. On the other hand, we can not write 9 in that manner for it can only be factored as 1*9 (in which case a would not be greater than 1) or as 3*3 (in which case the gcd would be 3).

Characterize those numbers which CAN NOT be written in this way, and prove your assertions.

HINT: Look at the numbers up through 20 to try to find a pattern.

So I went through the numbers up to 20.

I got:

1 no

2 no

3 no

4 no

5 no

6 yes, 3*2

7 no

8 no

9 no

10 yes, 5*2

11 no

12 yes, 3*4

13 no

14 yes, 2*7

15 yes, 3*5

16 no

17 no

18 yes, 9*2

19 no

20 yes, 4*5

So it is clear that primes can not be written in this way, and I am okay with proving this.

I think the numbers that can be written in this way can be written as a product of at least 2 unique primes. (i.e. 20=2*2*5, 6=3*2, but 16s prime factorization is 2^4). I am not entirely sure if this is correct, and I am having trouble proving it. Any help? Thanks.