Math for Computer Science

Question

I have a couple of questions on the material in "Mathematics for Computer Science" by Eric Lehman and Tom Leighton.

Q1. This is a theorem in the book:

Theorem 24. Let $p$ be a prime. If $p|a_1a_2 . . . a_n$, then $p$ divides some $a_i$. For example, if you know that $19 | 403 \bullet 629$, then you know that either $19 | 403$ or $19 | 629$, though you might not know which!

Why $p$ has to be a prime here? Doesn't this hold good for composite numbers as well? And Why $p$ has to divide only "some $a_i$" ? It can divide some or all of $a_i$ isn't it? Example: $3|9\bullet21\bullet81$

Q2: Here is a corollary in Section 4.3.5 Multiplicative Inverses in the book:

Let $p$ be a prime. If $k$ is not a multiple of $p$, then there exists an integer $k^{-1}$ $\in \{1, 2, . . . , p − 1\}$ such that: $k$$k^{-1}$ $\equiv 1 (mod p)$

Again why $p$ has to be prime here? I can say the same for composites as well right? Here is an example: $3\bullet5\equiv1 (mod 14)$

Can you please clarify on these? Thanks.

Answer 1

1. You need that $p$ is prime since otherwise this is just not true in general. Note: $$6 \mid 14 \cdot 9$$ but $6$ divides neither $14$ nor $9$. The "some" means "at least one."

2. Again, this is not true for composites in general. Try to find the value that makes $2 \cdot x \equiv 1 \pmod{14} $ true. You will notice it does not exist.

   However there would be a refinement/generalization for composite namely there is an inverse for $k \pmod{n}$ if $k$ is coprime with $n$, that is their gcd is $1$.

Answer 2

Q1: If $p$ is a prime it divides at least on of the $a_i$'s it can divide all of them, but at least one.

If $p$ is not a prime then we can't be sure. For example $4$ divides $28$ but it doesn't divide $2$ or $14$.

We need the number to be a prime for it to be guaranteed to work

Q2: Again, we need $p$ to be a prime. For example take $6$. $2$ does not have an inverse mod $6$ since no matter what we multiply $2$ by the resulting number will always be even, thus we can't reach $1$.