how would you solve 2x=5 (mod 7) 3x=4 (mod8)
Here's the catch: division is unique if the modulus is prime; otherwise, it can be multi-valued. So 5 / 2 mod 7 is unique, and equal to...
6, right?
what does 5/2 mean?
Five divided by two
What number, multiplied by 2, yields 5 when operating mod 7?
20?
Sure. But 20 = 6 mod 7
Notice that any value you can find which does so is 6 mod 7
That's the easier part.
The trickier part is 3x = 4 mod 8.
Let's think for the moment: if instead it were 2x = 4 mod 8, then both 2 and 6 would work, right?
That's because the 2, from 2x, divides the modulus
So division in modulo composite numbers may be multivalued. This led me to a wrong answer on an AIME problem, and I was mad
wow
Anyway, since 3 does not divide the modulus, 3x = 4 mod 8 has a unique solution, namely 6
what if x were 12?
Namely 4*, that was
and did you use a ≡ b mod m.
a – b = km
Here's what we now know (sorry for not using equivalent signs): x = 6 mod 7; x = 4 mod 8
With me?
how did you change the 5 to 6
Since 2x = 5 mod 7, x = 5/2 mod 7 = 6 mod 7, as above
(5/2 does not mean 2.5, it means "the number, which, upon multiplication by 2, yields 5 in modulo 7")
Anyway, we have two different equivalences for x in different moduli. Now comes the key point: the Chinese Remainder Theorem
(CRT)
It says: if you have a system of equations x = ai mod mi
And the mi are relatively prime
There there is a unique solution c such that x = c mod (m1*m2*m3*m4*...*mi)
It should make a bit of intuitive sense
If we know a certain number yields a certain remainder upon division by 3 and 5, say, then we know that it must have a unique remained upon division by 15.
right
Does this make sense?
some thanks though just started mods
Okay. So x = c mod (8 * 7), or x = c mod 56
So, can you find a c such that c = 6 mod 7 AND c = 4 mod 8?
(and c < 56)
Can't find a c
List the 6 mod 7 less than 56: 6, 13, 20, 27, 34, 41, 48, 55
List the 4 mod 8 less than 56: 4, 12, 20, 28, 36, 44, 52
Their intersection has exactly 1 element, as predicted by the CRT: 20
nice
So c = 20, and our solution is x = 20 mod 56
Note:
Although you can solve the original question just by guessing (does ? work, for ? up to 20)
The point is, if x = 20 mod 56, then x does not have to be 20
It can be 76
right
Or 76 + 56 * z, were z is an integer. All such values will solve your system
Sorry to go through this so fast, but that is, in short, how mods work.
yea ill have to look into it thanks! Im tired now
do u consider mods as easy?
Well, you already intuitively know a couple important mods: mod 2 (even/odd) and mod 10 (last digit). And I've been seeing them on math-competition type questions since freshman year, so I'd say they are a bit easier than things like cyclic quadrilaterals
They can get hard, however...
One sec
http://www.artofproblemsolving.com/Wiki/index.php/2013_AIME_I_Problems/Problem_11
I thought mods were easy, but this problem was a pure modular arithmetic one which I messed up somewhere
The key to my failure was this: part of the problem involves x = 3 mod 9
And trying to divide out the relevant parts (since x is already a multiple of 3, but unknown which one)
Anyway
You'll always see modular-type questions. If someone asks you for the last 2 digits of some giant product-like thing, think mod 100, or, by the CRT, mods 4 and 25