Let p be an element of {2,3,4…}. Sppose that for all x,y (integers) if xy ≡ 0 mod p, then x ≡ 0 mod p or y ≡ 0 mod p. Show p is prime.
I did some work on this problem but I have gotten stuck.
(p|xy => ((p|x or p|y)) => P is prime
Take the contrapositive:
≡ !(P is Prime) => !(p|xy => ((p|x OR p|y) for all integers x,y)
≡ (P = ab) => !(! p|xy OR (p|x OR p|y) for all integers x,y))
a, b integers > 1
≡ (P = ab) => (p|xy AND !((p|x OR p|y) for all integers x,y)))
≡ (P = ab) => (p|xy AND ((!p|x AND !p|y for all integers x,y)))
P = ab represents composite numbers. We take x = a and y = b. We have ab|xy and ab does not divide x or y.
I dunno I thought I was getting somewhere with it, but I don't know if I went down the right path to prove it or not or where to go from here.
Best Answer
Suppose to the contrary that $p\ge 2$ is composite (bigger than $1$ and not prime). Then there exist positive integers $x$ and $y$ such that $1\lt x\lt p$, $1\lt y\lt p$, and $xy=p$. (Informally, $p$ has a non-trivial factorization,)
Thus $xy\equiv 0\pmod{p}$. But since $x$ and $y$ are positive and less than $p$, we have $x\not\equiv 0\pmod{p}$ and $y\not\equiv 0\pmod{p}$. This contradicts the condition that if $xy\equiv 0\pmod{p}$ then $x\equiv 0\pmod{p}$ or $y\equiv 0\pmod{p}$.
Remark: If the symbols cause trouble, note for example that $70=7\times 10$. Let $x=7$ and $y=10$. Then $xy\equiv 0\pmod{70}$, but $x\not\equiv 0\pmod{70}$ and $y\not\equiv 0\pmod{70}$. Precisely the same sort of thing can be done with any composite number.