Find the lowest value of $x$ so that $x \in (A \setminus B)$

Question

Let $A$ and $B$ be two sets for which the following applies:

$A = \{x: \text{GCD(}x,12) = 1\}$
$B = \{x: x\ \text{is a prime}\}$

Find the lowest value of $x$ so that $x \in (A \setminus B)$.

$x \in A \setminus B$ means that $x \in A$ and $x \notin B$. So, $x$ is not a prime, and its greatest common divisor with 12 is 1...

How to solve?

Answer 1

Answer the literal question of "How to solve?" rather than "What is the answer?", I'd expect something like the following approach:

1. Find the first few members of each set, eg:

$$A = \{1,5,7,11,13,17,...\} \\ B = \{2,3,5,7,11,13,...\} $$

2. Clearly $1$ is the solution, but assuming for a moment that the question had forbidden it, we can think about the structure of the sets...

   • Set $A$ has a simple construction pattern ($12k+\{1,5,7,11\}$) but set $B$ we expect not to have a simple pattern from foreknowledge of primes
   • So why are we getting numbers in common?

3. Ideally here we'd see that the alternative view of $A$ is that it consists of all numbers coprime to both 2 and 3 - that is, it excludes only multiples of $2$ and $3$, and then link this to our knowledge of sieve methods for finding primes, which exclude multiples of all earlier members of the set of primes.

4. This gives us a characterization of $(A \setminus B)$: it is $\{1\}$ along with all composites with smallest prime factor $\ge 5$. And the second smallest member of that set is of course $25$ as already discussed.