# Thread: Characterizing numbers.....

1. ## Characterizing numbers.....

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.

2. Yes, that is correct. Try to prove it one direction at a time; first, prove that numbers which are divisible by more than one prime can be so written. Then show that numbers which can be so written are divisible by more than one prime (consider the prime factors of $a$ and $b$).

3. If I might offer an additional suggestion, maybe you can group the prime factors into two groups:

1. the first prime factor by itself, exponent included, and
2. all the others.

This way, the second group can contain an indefinite number of prime factors, and the gcd of the first and second groups will always be 1.