• Support PF! Buy your school textbooks, materials and every day products Here!

Disc. math/logic: division & modulus proofs

  • #1

Homework Statement


Show that if a, b, c, and d are integers such that a | c and b | d, then ab | cd.

Let m be a positive integer. Show that a mod m = b mod m if a ≡ b(mod m)


Homework Equations


| means "divides," so a | b means "a divides b" or "b can be divided by a"
mod gets the remainder; a mod m means "the remainder after m is divided by a"
≡ means "is congruent to"


The Attempt at a Solution


For the proof of the first one, I can easily substitute real values:
a = 4
b = 3
c = 16
d = 9

and from that I would get

(4)(3) | (16)(9)
12 | 144

which is obviously 12, for which the statement holds true; however, since this is a universal proof and not an existential one, that statement is far from enough to prove it.


For the proof of the second statement, I am unsure about how to treat a congruency in a proof like this.

Proofs are probably my weakest point in this course, so thanks in advance for any help.
 

Answers and Replies

  • #2
CEL
656
0
If a | c, then c = ma. In the same way, d = nb.
The rest of the demonstration is up to you.
 

Related Threads on Disc. math/logic: division & modulus proofs

  • Last Post
Replies
1
Views
743
  • Last Post
Replies
2
Views
743
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
1
Views
2K
Replies
6
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
1K
Top