mod arithmetic question (1 Viewer)

underthesun

N1NJ4
Joined
Aug 10, 2002
Messages
1,781
Location
At the top of Riovanes Castle
Gender
Undisclosed
HSC
2010
Just wondering, are we able to assume: (or is this the definition)
a = b (mod m)

means

a = km + b

where k is an integer?

It's for this question where I have to prove that:

if a = b (mod m) then gcd(a, m) = gcd(b, m).

Simple, but I've been skipping maths lectures ;)
 

Affinity

Active Member
Joined
Jun 9, 2003
Messages
2,064
Location
Oslo
Gender
Undisclosed
HSC
2003
from what you have

a = km + b

b = a - km

b is divisible by gcd(a,m)
similarly
a is divisible by gcd(b.m)

so gcd(a,m), gcd(b,m) are divisors of a,b and m

so gcd(a,m)<= gcd(b,m)
also gcd(b,m) <= gcd(a,m)
hence we conclude they are equal.

good luck next week
 

underthesun

N1NJ4
Joined
Aug 10, 2002
Messages
1,781
Location
At the top of Riovanes Castle
Gender
Undisclosed
HSC
2010
Thanks :). It's for discrete maths, but good luck for algebra too (you won't really need it though..)

You must be doing higher maths, but are you in higher computing as well? Cuz if you are, you happen to be in my class :p.
 

Affinity

Active Member
Joined
Jun 9, 2003
Messages
2,064
Location
Oslo
Gender
Undisclosed
HSC
2003
don't you guys have a DM test next week? I thought I heard that from my mates.
 

McLake

The Perfect Nerd
Joined
Aug 14, 2002
Messages
4,187
Location
The Shire
Gender
Male
HSC
2002
Originally posted by underthesun
Just wondering, are we able to assume: (or is this the definition)
a = b (mod m)

means

a = km + b

where k is an integer?
If you havn't already been shown this, you will be soon. It's a valid assumption ...
 

underthesun

N1NJ4
Joined
Aug 10, 2002
Messages
1,781
Location
At the top of Riovanes Castle
Gender
Undisclosed
HSC
2010
Originally posted by McLake
If you havn't already been shown this, you will be soon. It's a valid assumption ...
I just felt asleep during lectures :D

Originally posted by Affinity
don't you guys have a DM test next week? I thought I heard that from my mates.
That test was last week. Well.. good thing it's only very small %, so I dont have to make big deals out of my losses..
 

Users Who Are Viewing This Thread (Users: 0, Guests: 1)

Top