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.

  • $\begingroup$ Contradiction works...if $q$ is not a prime then $q=ab$ for $1<a,b<q$. Clearly $q$ does not divide either factor. $\endgroup$ – lulu Nov 3 '16 at 12:56
  • $\begingroup$ 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. $\endgroup$ – астон вілла олоф мэллбэрг Nov 3 '16 at 12:57
  • $\begingroup$ @астонвіллаолофмэллбэрг with that logic, 6 is also a prime number $\endgroup$ – onurcanbektas Nov 3 '16 at 13:03
  • $\begingroup$ 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. $\endgroup$ – астон вілла олоф мэллбэрг 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$.

  • $\begingroup$ I did not understand why they can not be true quietly ? $\endgroup$ – onurcanbektas Nov 3 '16 at 13:00
  • $\begingroup$ I don't understand what you are trying to say. $\endgroup$ – Dominik Nov 3 '16 at 13:01
  • $\begingroup$ :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 ? $\endgroup$ – onurcanbektas Nov 3 '16 at 13:01
  • $\begingroup$ 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. $\endgroup$ – Dominik Nov 3 '16 at 13:04
  • $\begingroup$ I'm sorry I guess my brain is stuck, but if $x > 1$, then y < q, so I still can't see the point. $\endgroup$ – 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.

  • $\begingroup$ what do you mean by "composite" ? $\endgroup$ – onurcanbektas Nov 4 '16 at 5:07
  • $\begingroup$ "Composite" means "not a prime number nor $1$". $\endgroup$ – user378947 Nov 4 '16 at 15:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.