0

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.

Our
  • 7,285
  • 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 03 '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. – Sarvesh Ravichandran Iyer Nov 03 '16 at 12:57
  • @астонвіллаолофмэллбэрг with that logic, 6 is also a prime number – Our Nov 03 '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. – Sarvesh Ravichandran Iyer Nov 03 '16 at 13:04

2 Answers2

1

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

Dominik
  • 19,963
  • I did not understand why they can not be true quietly ? – Our Nov 03 '16 at 13:00
  • I don't understand what you are trying to say. – Dominik Nov 03 '16 at 13:01
  • :D "But neither of these can be true, since x=py<p x = p y < p by the assumption y>1 y

    1 resp. y=px<p y = p x < p by the assumption x>1 x

    1 ." What do you mean by that ?

     – Our Nov 03 '16 at 13:01
  • 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 03 '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. – Our Nov 03 '16 at 13:07
  • $y < q$ implies that $q$ is not a divisor of $y$. Similarly, $q$ is also not a divisor of $x$. This is a contradiction to the assumption that $q|x$ or $q|y$ must hold. – Dominik Nov 03 '16 at 13:09
  • yes, but it also holds for $6=2*3$ ? – Our Nov 03 '16 at 13:12
  • And $6$ is also not a prime number. Please take your time to think precisely about the proof before you post further comments. – Dominik Nov 03 '16 at 13:13
  • After a good sleep, I got it :) – Our Nov 04 '16 at 05:08
0

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.