Question

prove that if n is composite then there are integers a and b such that n divides ab, but n does not divide either a or b.

Answer 1

let n be the given composite numbers,, hence n > 3

now since n is composite the prime factorization of n is possible.

let the prime factorization of n has primes from the set P = { p₁ , p₂ , ...., p_m } with multiplicities a₁ , a₂ , ..., a_m

now, consider, two partitions of P as P₁ and P₂

let, a and b have prime factorizations from P₁ and P₂ respectively and the prime factorization of a and b from P have multiplicities of the primes greater than a_i for all i in {1,2,...,m}

hence, the product ab has all the primes in P but with higher multiplicities than that of n

hence, n can not divide either of a and b

but the product ab has all the primes in P and have multiplicities greater than all the a_i for all i in {1,2,...,m}

hence n divides the product ab but n does not divide a and b individually