Test Tommorow, Urgent Discrete Math advice needed.

Printable View

February 20th 2008, 03:57 PM
p00ndawg

Test Tommorow, Urgent Discrete Math advice needed.

Having my first exam tomorrow, and while Im prepared, im finding that problems with modulus arithmetic are giving problems.

For example, prove that if ac =(congruent) bc (mod m), then a =(congruent) b (mod m/d), where d = gcd(m,c).

I was wondering if anyone could give me any tips for these types of problems?

This was a review question, and i WILL have a question like this on my exam tomorrow.

thanks!

btw i have the answer for the question, but just provided it as an example. I understand the theory and what it means, just being able to prove it one way or another is proving to be difficult.
February 20th 2008, 05:18 PM
Jhevon

Quote:

Originally Posted by p00ndawg

Having my first exam tomorrow, and while Im prepared, im finding that problems with modulus arithmetic are giving problems.

For example, prove that if ac =(congruent) bc (mod m), then a =(congruent) b (mod m/d), where d = gcd(m,c).

I was wondering if anyone could give me any tips for these types of problems?

This was a review question, and i WILL have a question like this on my exam tomorrow.

thanks!

btw i have the answer for the question, but just provided it as an example. I understand the theory and what it means, just being able to prove it one way or another is proving to be difficult.

the best way to tackle these is to learn how to write them without congruences. that is, if you are unfamiliar with manipulating congruences themselves. when you have a set of equations working with, it is usually easier to "see" what you need to do. write out what the statements mean and then write out what you want to show.

the problem asked you to prove $ac \equiv bc~(\mbox{mod }m) \implies a \equiv b~(\mbox{mod }m/d)$ , where $d = \mbox{gcd}(m,c)$

so $ac \equiv bc~(\mbox{mod }m)$ means $c(a - b) = km$ for $k \in \mathbb{Z}$ (i suppose you know how to get to this equation)

you are required to use the equation above to show that $a \equiv b~(\mbox{mod }m/d)$ that is, you want to show $a - b = \frac {\alpha m}d$ for some $\alpha \in \mathbb{Z}$

since $d = \mbox{gcd}(m,c)$ , we can get the desired result by dividing the first equation through by $d$ and simplifying
February 20th 2008, 05:39 PM
p00ndawg

Quote:

Originally Posted by Jhevon

the best way to tackle these is to learn how to write them without congruences. that is, if you are unfamiliar with manipulating congruences themselves. when you have a set of equations working with, it is usually easier to "see" what you need to do. write out what the statements mean and then write out what you want to show.

the problem asked you to prove $ac \equiv bc~(\mbox{mod }m) \implies a \equiv b~(\mbox{mod }m/d)$ , where $d = \mbox{gcd}(m,c)$

so $ac \equiv bc~(\mbox{mod }m)$ means $c(a - b) = km$ for $k \in \mathbb{Z}$ (i suppose you know how to get to this equation)

you are required to use the equation above to show that $a \equiv b~(\mbox{mod }m/d)$ that is, you want to show $a - b = \frac {\alpha m}d$ for some $\alpha \in \mathbb{Z}$

since $d = \mbox{gcd}(m,c)$ , we can get the desired result by dividing the first equation through by $d$ and simplifying

Thanks, so it general a question similar to this, the first part needs to be used to prove the second?
February 20th 2008, 05:49 PM
Jhevon

Quote:

Originally Posted by p00ndawg

Thanks, so it general a question similar to this, the first part needs to be used to prove the second?

yes. whenever you see IF ... THEN ---. you have what we call an implication

it means you have to use ... to prove ---

or by the contrapositive, you can assume NOT --- and use it to prove NOT...
February 20th 2008, 06:06 PM
p00ndawg

Quote:

Originally Posted by Jhevon

yes. whenever you see IF ... THEN ---. you have what we call an implication

it means you have to use ... to prove ---

or by the contrapositive, you can assume NOT --- and use it to prove NOT...

thanks this helps a bit.

I still sometimes just get stuck on the very last part, I guess you could call it the "inductive" part of the problem.

(Headbang)
February 20th 2008, 06:21 PM
Jhevon

Quote:

Originally Posted by p00ndawg

thanks this helps a bit.

I still sometimes just get stuck on the very last part, I guess you could call it the "inductive" part of the problem.

(Headbang)

it may help for you to be a little more specific. are you having trouble with the last part of this problem? maybe there's another problem that was giving you trouble. you may want to post it and state your difficulties...
February 20th 2008, 07:01 PM
p00ndawg

Quote:

Originally Posted by Jhevon

it may help for you to be a little more specific. are you having trouble with the last part of this problem? maybe there's another problem that was giving you trouble. you may want to post it and state your difficulties...

prove that n^4 is congruent to(mod5).

5 does not divide n.

also a problem like this, show that if a, b, and c are intergers where c does not equal 0, such that ac divides bc, then a divides b.

I guess I have problems understanding why. I understand how to set them up, but having trouble putting it together.
February 20th 2008, 07:09 PM
Jhevon

Quote:

Originally Posted by p00ndawg

prove that n^4 is congruent to(mod5).

5 does not divide n.

congruent to what?

Quote:

also a problem like this, show that if a, b, and c are intergers where c does not equal 0, such that ac divides bc, then a divides b.

I guess I have problems understanding why. I understand how to set them up, but having trouble putting it together.

remember this.

all these statements are equivalent:

$a \equiv b~(\mbox{mod }n)$

$n~|~a - b$ which is the same as saying $n~|~b - a$

$a - b = kn$ for some $k \in \mathbb{Z}$

with that being said. we have an IF, THEN statement here. i already told you how to deal with that. here we opt for the "direct proof." that is, we will use the first statement to prove the second.

recall from above, $ac~|~bc$ means $bc = k(ac)$ for $k \in \mathbb{Z}$

we want to use this to show $a~|~b$ , that is, $b = \alpha a$ for $\alpha \in \mathbb{Z}$ .

since $c \ne 0$ , we can divide by it. dividing the first equation by c we get the desired result