- #1

- 32

- 0

## Homework Statement

Disprove the following assertion: "There exist distinct positive integers a and b such that for all natural numbers n we have (a,n)=1 or (b,n)=1."

## Homework Equations

(a,n)=1 and (b,n)=1 means greatest common divisor of a and n is 1, and of b and n is 1, respectively.

## The Attempt at a Solution

This was my attempt at a solution. My teacher said it was wrong. Not really sure why.

Suppose there exists such a and b that are natural numbers where a isn't equal to b, a and b aren't equal to 1, where for all n that are natural numbers we have (a,n)=1 or (b,n)=1. Since a isn't equal to 1, we have that there's a prime divisor of a, i.e. p1=P. Since b isn't equal to 1, we have that there's a prime divisor of b, i.e. p2=P. Take n=p1*p2. Then p1 divides (a,n) where (a,n)>1, and p2 divides (b,n) where (b,n)>1 which is a contradiction.