# Perfect divisibility for products in modular arithmetic

Say we have that

$z^2 - x^2 = 0 \ ( \ mod \ p)$

that implies:

$p \ | \ (z-x)(z+x)$

However I was not 100% sure how that implies about the divisibility of p towards $(z-x)$ and/or $(z+x)$ and whether it depends if p is prime or not. The notes I was reading says that "because p is prime, then it divides $(z-x)$ or $(z+x)$". However, say that we have two numbers $n_1$ and $n_2$ and:

$$n_1n_2 = 0 \ ( \ mod \ p)$$

and thus:

$$p \ | \ n_1n_2$$

I thought that always implied, regardless of whether p is prime or not, that p either divided $n_1$ or $n_2$. Or am I wrong? Why does p have to be prime? I was suspecting that maybe it had something to do with having multiplicative inverses and $gcd(x,p) = 1$ only being true if p was prime, what I was not sure honestly.

Also, if n is composite, then what do we know if $n \ | \ n_1n_2$? Also, if n is composite, and we know $n \ | \ n_1n_2$, then, does it necessarily mean it must divide either $n_1$ or $n_2$?

I guess I am trying to understand the fundamental reason why p has to be prime for it to divide at least one of them (i.e. what makes p prime special).

Just for reference, this question came from solving the simple quadratic equation I wrote at the top and quadratic residues.

You are on the right track. This divisibility property is true iff the divisor is prime, namely

Theorem $\$ If $\,a>1\,$ is a natural number then

$$a\ \ {\rm is\ prime}\,\ \iff\,\ a\mid bc\, \Rightarrow a\mid b\ \ {\rm or}\, \ a\mid c,\ \ {\rm for\ all}\,\ b,c\in \Bbb N$$

Proof $\ (\Rightarrow)\ \$ If $\,a\,$ is prime and $\,a\mid bc\,$ then $\,ad = bc\,$ for some $\,d\in \Bbb N.\,$ Taking prime factorizations of $\, ad = bc\,$ and invoking uniqueness of prime factorizations, we infer that the prime $\,a\,$ must occur in either the (unique) prime factorization of $\,b\,$ or $\,c,\,$ hence $\,a\mid b\,$ or $\,a\mid c.$

$(\Leftarrow)\ \$ If $\,a\,$ is not prime then $\,a = bc,\,$ for some $\,1< b,c\in \Bbb N.\,$ Then $\,a\mid bc,\$ but $\,a\nmid b,c.\ \$ QED

• I'm not sure if I understood the other direction. For the second direction, are we proving that if $a \ | \ bc$ then a is prime? I am not sure what the goal was for the second direction. Also, are you doing it by using contrapositive? Jan 11, 2014 at 22:13
• @Pinocchio The direction $(\Rightarrow)$ is the rightward direction in the claimed $(\!\!\iff\!\!)$ equivalence, i.e. primes satisfy said divisibility law for all $\,b,c.\,$ The $(\Leftarrow)$ is the opposite direction, that if the divisibility law holds for all $b,c\,$ then $a$ is prime. I proved the contrapositive, that if $a$ is not prime (i.e. composite) then there are some $a,b$ for which the law fails. Jan 11, 2014 at 22:45

Primality is sufficient as $$4\cdot 6|9\cdot8$$ but $$4\cdot 6\not|9 \text{ or }4\cdot 6\not|8$$

More generally if $p=p_1^2p_2^3$ and $n=p_1^4p_2^5$ where $p_1,p_2$ are primes

Observe that $p$ divides $n$ but not $p_2^5$ or $p_1^4$

Another point if prime $p>3$ divides both $z+x,z-x$

$p$ will divide $z+x\pm(z-x)\implies p$ will divide $2x$ and $2y$

$\implies p$ will divide $(2x,2y)=2(x,y)$

Hence, $x,y$ must be divisible by $p$

• If n is composite, then what do we know if $n \ | \ n_1n_2$? Also, if n is composite, and we know $n \ | \ n_1n_2$, then, does it necessarily mean it must divide either $n_1$ or $n_2$? Jan 11, 2014 at 8:27
• @Pinocchio, have you noticed my example, $4\cdot6$ does not divide $9$ and $8$ individually, but $4\cdot6$ divides $9\cdot8$ Jan 11, 2014 at 8:28
• @Pinocchio, also if $n|n_1\cdot n_2,$ we can only say for sure that $n|n_1$ if $(n,n_2)=1$ Jan 11, 2014 at 8:33
• I guess I am trying to understand the fundamental reason why p has to be prime for it to divide at least one of them (i.e. what makes p prime special). Is it because, if p is prime and $p \ | \ n_1n_2$, then it has to be relatively prime to at least one factor but not both...right? Jan 11, 2014 at 8:44
• @Pinocchio, no, for example $3$ divides $12\cdot15,3$ divides both $12,15$. The point is as prime $p$ does not have any prime factor other than itself, it must belong to at least one of $n_1,n_2$ as factor Jan 11, 2014 at 9:04