How to prove or disprove: "If $ab\equiv 0 \pmod 7$, does that mean $a\equiv 0 \pmod 7$ or $b\equiv 0 \pmod 7$?"

Question

I have a homework problem for an introductory proofs class that asks the question in the title for $a,b\in\mathbb{N}$, asking also for the student to justify their answer.

It's clear to me that the question can be rephrased more simply as "If $7\mid ab$, does that mean $7\mid a$ or $7\mid b$?" So, I tried to prove that instead. I tried the following proof, but I'm almost certain that it's incorrect:

---

Proof. Suppose that $7\mid ab$ for some $a,b\in\mathbb{N}$. Then, $$ab = 7k$$ for some $k\in\mathbb{Z}$. Suppose $k = mn$, for $m,n\in\mathbb{Z}$, which makes $ab = 7mn$. Going by cases, we have that either

1. $a = 7m$, $b = n$, or
2. $a = n$, $b = 7m$.

So, either $7\mid a$ or $7\mid b$.

---

The next problem on my homework asks to consider whether $6\mid ab$ implies $6\mid a$ or $6\mid b$; by this logic, it seems true since replacing 6 for 7 doesn't really change the logic of the proof, but my friends in the class told me that the second question is wrong. So, I'm assuming that my attempt at a proof is missing some complexity that I'm not seeing at the moment.

Is this the correct direction to go for a proof like this, or is there a way that's more straightforward? If this is the right direction, how could I make it more rigorous, and use a similar method to prove/disprove the next statement in my homework?

Answer 1

Suppose that $7\mid ab$ and $7\nmid a$. Now, we want to show that $7\mid b$.

Since $7\nmid a$ and $7$ is a prime, we get that $(7,a)=1$. By Bezout's Identity, there exists $r,s\in\mathbb{Z}$ such that $$7r+sa=1$$

Multiplying both sides by $b$, we get $$7rb+sab=b$$

Since $7\mid7rb$ and $7\mid ab \implies 7\mid sab$, we get that the LHS is divisible by $7$. Hence, the right hand side must be divisible by $7$, so $7\mid b$, and we're done.

What this shows is that if any one of $a,b$ is not divisible by $7$, then the other must be divisible by $7$, which implies that $7\mid a$ and/or $7\mid b$.

Answer 2

For any prime $p$ such that $p\mid ab$ then either $p\mid a$ or $p\mid b$ thats due to the fundamental theorem of arithmetic any number can be written uniquely as product of primes. So if $a=\prod_{i=1}^n p_i^{e_i}$ and $b=\prod_{j=1}^m p_j^{e_j}$ and $k = \prod_{r=1}^s p_r^{e_r}$ then we have $$\prod_{i=1}p_i^{e_i} \prod_{j=1}^m p_{j}^{e_j} = p \prod_{r=1}^s p_r^{e_r}$$ By the uniqueness we should have $p_i = p$ for some $i$ or $p_j = 7$ for some $j$.

For the case of composite numbers thats not true clearly $6\mid 12 $ but $6\mid 4(3)$ but neither $6\mid 4$ nor $6\mid 4$

Edited (Just copied Nicholas solution):

Assume $p\mid ab\Rightarrow ab=pk$ for some $k$ and assume that $p\nmid d a$ then $gcd(a,p) =1$ so by Bezout identity there exists $x,y$ such that $ax+py =1 $ multiply with $b$ we get $abx + bp y = b$ implies $p(kx + by) = b$ so $p\mid b$