Definition: x | y (x divides y)
For x ∈ Z, x ≠ 0; y ∈ Z
x | y ⇔ ∃z ∈ Z such that xz = y
1. If a | b, then a | bc for all c (where c is an integer)
Prof. Conrad solved this one in class on Monday, but here is a more clear version.
We are trying to prove a | bc
That means
we are looking to prove ∃j∈ Z such that ja= bc
To find it, we convert the statement a|b into an equation by appying the definition. We work with that equation until we get one that is in the form we need, that is some integer j times a on the left, and bc on the right. This same techinque can be applied to the three other problems below as well.
| step number | step | justification |
| (1) | a|b | given |
| (2) | ∃k∈ Z such that ak=b | definition of divides (|), using ⇒ |
| (3) | ∀c∈Z, akc = bc | algebra (multiply both sides by c) |
| (4) | Let j=kc | defining a variable |
| (5) | ∃j∈ Z such that ja=bc | combine steps 3 and 4 into the form of the right hand side of the definition of divides |
| (6) | a|bc | defintion of divides (|), using ⇐ |
Now, you try to prove these three theorems from the notes in class on Monday
2. If a | b and b | c, then a | c
We are trying to prove a |c
That means
we are looking to prove ∃d∈ Z such that ad = c
| step number | step | justification |
| (1) | a|b, b|c | given |
| (2) | ∃k∈ Z such that ak=b ∃j∈ Z such that bj=c |
definition of divides (|), using ⇒ |
| (3) | akj = c | algebra (substitute ak in for b in the equation bj = c) |
| (4) | Let d = kj ∃d∈ Z such that ad=c |
defining a variable d |
| (5) | a|c | defintion of divides (|), using ⇐ |
3. If a | b and a | c, then a | sb + tc for all s and t.
We are trying to prove a | sb + tc, for all s and t
That means we are trying to prove ∃d∈ Z such that ad = sb + tc
| step number | step | justification |
| (1) | a|b,a|c | given |
| (2) | ∃k∈ Z such that ak=b ∃j∈ Z such that aj=c |
definition of divides (|), using ⇒ |
| (3) | ∀s, sak = sb, ∀t, taj = tc | algebra (multiply both sides of equations by the same number, s in one case, t in the other) |
| (4) | sak + taj = sb + tc | algebra (add the equations together) |
| (5) | a(sk + tj) = sb + tc | algebra (factor out a) |
| (6) | Let d = (sk + tj) ∃d∈ Z such that ad=sb + tc |
defining a variable d |
| (7) | a | (sb + tc) | defintion of divides (|), using ⇐ |
4. For all c ≠ 0, a | b if and only if ca | cb.
This is an if and only if, so we have to do two proofs!
Part 1 (⇒)
We are trying to prove ca | cb
That means we are trying to prove ∃d∈ Z such that dca = cb
| step number | step | justification |
| (1) | a|b | given |
| (2) | ∃k∈ Z such that ak=b |
definition of divides (|), using ⇒ |
| (3) | ∀c ≠ 0, cak = cb |
algebra (multiply both sides of equations by the same number c, then rearrange factors on left hand side) |
| (6) | Let d = k ∃d∈ Z such that dca=cb |
defining a variable d |
| (7) | ca | cb | defintion of divides (|), using ⇐ |
Part 2 (⇐)
We are trying to prove a | b
That means we are trying to prove ∃d∈ Z such that ad=b
| step number | step | justification |
| (1) | ca|cb | given |
| (2) | ∃k∈ Z such that cak=cb |
definition of divides (|), using ⇒ |
| (3) | ∀c ≠ 0, cak = cb → |
algebra (divide both sides by a quantity that is not zero) |
| (6) | Let d = k ∃d∈ Z such that ad=b |
defining a variable d |
| (7) | a|b | defintion of divides (|), using ⇐ |