1

Let $p\in\{2,3,4,\dots\}$. Suppose that $\forall x,y\in\mathbb Z\ p\mid xy\implies p\mid x\lor p\mid y$. Show that $p$ is prime.

I am not fully understanding this problem. If I input numbers into the equation so for example $x = 5, y = 10$ and $p = 10$ then $p$ is clearly not prime, but it does divide the product of 5 and 10. Am I suppose to assume that $p$ is prime? if that's the case why do I have to show that $p$ is prime? Thanks.

Parcly Taxel
  • 103,344
fsdff
  • 235
  • You seem to be forgetting one of the most important phrases in the problem., for all. Although $10$ does indeed divide $x\cdot y$ as well as divides $x$ or $y$ in the case that $x=5$ and $y=10$ it is not true that $10$ divides into $x$ or $y$ in the case that $x=5$ and $y=2$ despite $10$ dividing into $x\cdot y$. – JMoravitz Jan 31 '18 at 06:44
  • 1
    The statement that you are asked to prove is in fact the usual definition of being a prime number that I and many other people encourage. Before we can continue much further, what definition of prime are you working with? Perhaps that $p$ has no positive divisors other than itself and $1$? – JMoravitz Jan 31 '18 at 06:45
  • Why not? does 10 not divide into 10? I am using the definition that most people use. – fsdff Jan 31 '18 at 06:48
  • @JMoravitz sorry forgot to tag – fsdff Jan 31 '18 at 06:55
  • Yes 10 divides into 10. 10 does not divide into 5 however, nor does it divide into 2. This is in spite of $10$ dividing evenly into the product of $5$ and $2$. As such, 10 is not a prime number. As for "I am using the definition that most people use" that is painfully ambiguous. You should very explicitly and in full detail say what definition of prime numbers you are using. The definition I use (and most anyone I've worked with) is again precisely the statement above: $p$ is prime if and only if for all $x,y\in\Bbb Z$ one has $p\mid xy\implies p\mid x$ or $p\mid y$. – JMoravitz Jan 31 '18 at 06:56
  • Using that definition, there nothing to prove because what you are asked is the definition of primeness in the first place. – JMoravitz Jan 31 '18 at 06:59
  • @JMoravitz but in my example I did not use 5 and 2 I used 5 and 10. – fsdff Jan 31 '18 at 07:00
  • I doubt you know "most people" and thus the definition they use, and it's not uncommon to learn that the definition you've learned is not common. – Henrik supports the community Jan 31 '18 at 07:04
  • And I point out again, the problem begins "Suppose that for all $x,y$". You can have some pairs $(x,y)$ such that $p\mid xy\implies p\mid x\vee p\mid y$ is actually a true implication, but it must be true for all pairs to be prime. Yes $10\mid 50\cdot 13$ while $10\mid 50$ is true. Yes $10\mid 3\cdot 20$ while $10\mid 20$ is true. However $10\mid 5\cdot 2$ is true while both $10\mid 5$ is false as well as $10\mid 2$ is false, so $10$ is not prime. Compare this to an actual prime number such as $2$. $2\mid x\cdot y$ does in fact imply that $2\mid x$ or $2\mid y$ for all $x,y$. – JMoravitz Jan 31 '18 at 07:04

3 Answers3

1

Let's unpack "$\forall x,y\in\mathbb{Z}, p\mid xy\implies p\mid x\lor p\mid y$" a little.

This says,

  • First write down all possible pairs $(x,y)$ where $x$ and $y$ are both in $\mathbb{Z}$.
  • Now throw most of them away, keeping only the ones where $p \mid xy$.
  • Of the surviving pairs, are any a witness to the falsehood of "$p\mid xy\implies p\mid x\lor p\mid y$"? To be such a witness, we must have a pair $(x,y)$ that makes "$p\mid xy$" true (which we've arranged by throwing out the pairs that do not do so) while also making "$p\mid x\lor p\mid y$" false.

You are to show that the absence of witnesses to falsehood forces that $p$ is prime. Equivalently, by contraposition, you are to show that $p$ not a prime forces the existence of a witness of falsehood.

Working through a simple example can suggest an outline of the proof. As an example of showing the contrapositive version, the choice $p=6$ is not prime. Now take $x = 2$, $y=3$. We see that $p = 6 \mid 6 = 2 \cdot 3 = x y$. However, $p = 6 \not\mid 2 = x$ and $p \not\mid 3 = y$. Consequently, the pair $(2,3)$ is a witness to the falsehood of the implication when $p = 6$. So for this particular choice of not prime $p$, we have shown that there is a witness to falsehood of the implication. How would you modify this argument to work for an arbitrary not prime $p$?

Eric Towers
  • 67,037
0

Do it by induction on the number of primes dividing $xy$.

If two primes divide $xy$, then one must be $x$ and the other must be $y$. Since $p$ divides one of these, it is prime.

If $n+1$ primes divide $xy$, then both $x$ and $y$ have at most $n$ primes dividing them. By the induction hypothesis, whichever $p$ divides forces $p$ to be prime.

marty cohen
  • 107,799
0

If $p$ is not prime, write $p=rs$... Then $p|rs$, but $p\not|r \text { and } p\not|s$