Proof using smallest counter example

Question

Prove that any integer $n > 1$ is divisible by a prime using smallest counterexample

I got about halfway through this proof. I assumed that there was a smallest number $x$ (with $2$ being the base case) which cannot be divided by any prime number. Then I considered $x-1$, which is true.

Then I broke this question into two cases:

Case 1: $x-1$ is odd. Then, $x-1+1=2k+1+1$, which means that $x=2(k+1)$. This goes against my assumption as this expression is divisible by $2$, which is prime.

Case 2: $x-1$ is even. Then, $x-1+1=2k+1$, $x=2k+1$ – I am currently stuck here.

I'm currently stuck on the 2nd case. Any advice? Thanks!

Answer 1

@Ethan Bolker already gave a very strong hint. My answer's purpose is solely to try and give a better intuition as to how one would get there alone.

In proofs that make use of induction or some form of it, the key is always being able to reduce a problem to a smaller one. The "key of that key" is finding the type of relation you want to establish!

We are working with factorizations and primes and number divisions. We know that for any integer $x$, $x $ and $x-1$ are coprime.

(This can be show by first proving $\operatorname {gcd}(a, b) = \operatorname {gcd}(b, a-b) $ and then making $a=x, b=x-1$ to conclude $\operatorname{gcd} (x, x-1)=1$)

That is, they share no factors. This means it is always a very difficult problem to relate the factors of $x $ and $x-1$. Therefore the key to solving your problem won't be considering $x-1$.

Then you should be able to relate $x $ to some smaller number without means of subtraction. You are then left with your second most obvious choice that is division.

You suppose you can't divide $x $ by any prime. First be sure $x $ itself is not prime. If it were, there would be nothing to be done. If it is not, you would want to show that $\frac{x}{b} = a$ because for the right $a, b $ you can then make use of the fact that smaller numbers than $x $ have prime factors.

You should now try to make use of my hint or Ethan's and solve the problem. If no further progress can be made I will then be glad to provide more explicit help.

Answer 2

Hint. Trying to show $x$ is a counterexample by looking just at $x-1$ isn't working (as you point out). Here's a way around that. If $x$ is prime you're done, since it divides itself so it's not a counterexample. If it's not prime then you can write $x = ab$ in a nontrivial way. What can you say about $a$ and $b$?