# Show that $q$ is prime

Let q be a positive integer such that $q \geq 2$ and such that for any integers $a$ and $b$, if $q|ab$ then $q|a$ or $q|b$.Show that $q$ is a prime number.

It will probably be proved by contradiction, so I assumed $q$ is a prime, i.e $q=xy$ where $x$ and $y$ are some positive integers and not equal to $1$ or $q$, and tried to a contradiction but I couldn't figure out how to proceed from here.

• Contradiction works...if $q$ is not a prime then $q=ab$ for $1<a,b<q$. Clearly $q$ does not divide either factor. – lulu Nov 3 '16 at 12:56
• If $q=xy$, where $xy$ are not equal to $1$ or $q$, then isn't that a contradiction, because of course $q$ doesn't divide either $x$ or $y$? (it is larger than both of them). So if $x,y$ take the place of $a,b$ in the yellow box then you have a contradiction. – астон вілла олоф мэллбэрг Nov 3 '16 at 12:57
• @астонвіллаолофмэллбэрг with that logic, 6 is also a prime number – onurcanbektas Nov 3 '16 at 13:03
• But $6 = 2*3$, whereas $6 \nmid 2$ and $6 \nmid 3$! So it does not hold true that for every pair of numbers $a,b$, $6 |ab$ implies $6|a$ or $6|b$. Let us sort out this confusion quickly. – астон вілла олоф мэллбэрг Nov 3 '16 at 13:04

It is correct that this can be proven via contradiction. If $q$ is not a prime, then we can find two integers $x, y > 1$ such that $q = xy$. But this means $q|xy$, so by our assumption we have $q|x$ or $q|y$. But neither of these can be true, since $x = \frac{q}{y} < q$ by the assumption $y > 1$ resp. $y = \frac{q}{x} < q$ by the assumption $x > 1$.
• We have $x > 1$, so this means $y = \frac{q}{x} < q$. But this implies that $q$ does not divide $y$, since a divisor of a positive integer can't be greater than the integer itself. – Dominik Nov 3 '16 at 13:04
• I'm sorry I guess my brain is stuck, but if $x > 1$, then y < q, so I still can't see the point. – onurcanbektas Nov 3 '16 at 13:07
Suppose $q$ is composite. Then you can write $q=nk$ for some $n,k\geq2$. Clearly $q|nk$ as every natural number divides itself, which implies by hypothesis that $q|n$ or $q|k$. In particular $q\leq n$ or $q\leq k$ which is a contradiction.
• "Composite" means "not a prime number nor $1$". – user378947 Nov 4 '16 at 15:01