# Proof using smallest counter example

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!

• Effectively this is a tautology. Either it's a prime which can be divided by itself, or it's a compound number which can be divided by any of its prime factors. What a silly question (for your professor to ask). – Wildcard Feb 21 '17 at 3:51

## 2 Answers

@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.

• Thanks guys! This is my first time with math stack exchange so I'm surprised it worked so well. I'll give it a shot and see how far I get. Will post question again if I can't figure it out. – richcao Nov 10 '16 at 0:50
• @richcao Your question got some attention because you explained what you'd tried. If you're still puzzled, don't repost. Either edit the question (at the end) or ask in a comment about where you get stuck. – Ethan Bolker Nov 10 '16 at 0:56
• Whoops sorry--i meant I'll post a comment or something at the end. Thanks again! – richcao Nov 10 '16 at 1:01
• @RSerrao Correct me if I'm wrong, but the way I did it was this. I said x was composite and therefore it cannot be prime itself and must equal ab where a and b are positive ints that are less than x. Either a, or b, or a and b can be prime in which case the proof is done. In the other case, both a and b are compositie, but since a and b are smaller than x, and x is the smallest case where such a number does not have a prime factor, a and b must each have a prime factor and therefore the proof is done. – richcao Nov 10 '16 at 22:20
• @richcao you are totally right. Feel free to accept the answer if you think it was the right answer. – RGS Nov 10 '16 at 22:27

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$?

• I thought about that. $x = ab$. To what extent can we use that? It seems like we are kind of using the same thing we are proving in a surreptitious way. Is this logically fine? In this case I mean – RGS Nov 10 '16 at 0:12
• You can use the fact that $x$ factors (since it's not prime) but you can't assume $a$ or $b$ is a prime (which would be surreptitious). You can say something useful about each that will lead to the desired contradiction. – Ethan Bolker Nov 10 '16 at 0:17
• I know how to proceed from there. I just didn't know you could flat out say $x = ab$. – RGS Nov 10 '16 at 0:17
• @RSerrao The username on the comments doesn't match the username on the question. One person or two? – Ethan Bolker Nov 10 '16 at 0:20
• we are two different people! I was just trying to answer the question without making use of your hint and decided to ask you if we could use it without spoiling the purpose of the proof – RGS Nov 10 '16 at 0:21