Question

FAN AND MEDAL WILL BE REWARDED:
Solve this system of congruences
2x=5 (mod 7)
3x=4 (mod 8)

Answer 1

i basically only need to know how to make the 2x and 3x into single x's.

Answer 2

not sure how to explain but I got an answer

for the first, x must be equivalent to 6 + 7k, k = 0,1,2,...

Answer 3

would you happen to know how to make the x's into a workable form, i mean into just x??

Answer 4

for the second, x must be equivalent to 4 + 8m, m = 0, 1, 2, ...

Answer 5

x is 5

Answer 6

lol just learned it online

Answer 7

need explanation?

Answer 8

how is x = 5? 2*5 = 10 = 3 mod 7

Answer 9

where do we get 3 mod 7 though?

Answer 10

jeff, yeah thanks that would be great.

Answer 11

http://www.math.rutgers.edu/~erowland/modulararithmetic.html

Answer 12

dude, 20 is the first x that works... not 5

Answer 13

basically a ≡ b mod m. means you do a-b=km

Answer 14

idk lol I just solved the system with k and x as variables ok maybe you know it better

Answer 15

alright just one sec im gonna try some work real quick

Answer 16

ok 5 doesn't work haha

Answer 17

40 does nice job

Answer 18

so i start with 2x-5 = 7 times k?

Answer 19

because i cant really solve further than that

Answer 20

1 sec asking friend

Answer 21

alright thanks

Answer 22

Think about equivalence classes

2*0 = 0 (mod 7)
2*1 = 2 (mod 7)
2*2 = 4 (mod 7)
2*3 = 6 (mod 7)
2*4 = 1 (mod 7)
--------------
2*5 = 3 (mod 7)
--------------
2*6 = 5 (mod 7)

3*0 = 0 (mod 8)
3*1 = 3 (mod 8)
3*2 = 6 (mod 8)
3*3 = 1 (mod 8)
--------------
3*4 = 4 (mod 8)
--------------
3*5 = 7 (mod 8)
3*6 = 2 (mod 8)
3*7 = 5 (mod 8)

2x=5 (mod 7)
3x=4 (mod 8)

Answer 23

have a look

Answer 24

so then how would i come up with just x though? i meant tkhunny that was great but

Answer 25

x=20mod56 dont ask why

Answer 26

my friend gave a huggge explanation that is like 20 fb messages

Answer 27

lol dude i need the work thats most of the points!! haha thanks tho

Answer 28

do you think you could like copy the messages??

Answer 29

It's so hard...i dont think its worth it..uses chinese remainder theorem

Answer 30

haha nvm then thanks

Answer 31

wed. what class is this for?

Answer 32

algebra 2 trig

Answer 33

wait your in algebra 2? Im in calc 3 and diff eq...

Answer 34

This is where the thinking I suggested might have take you...

With a little luck, there is a multiplicative inverse for each value presented.

2x=5 (mod 7)

2*4 = 1 (mod 7)
(Everyone has an inverse (mod 7))

4*2*x = 4*5 (mod 7)

x = 6 mod 7

3x=4 (mod 8)

3*3 = 1 (mod 8)
(Only 1, 3, 5, and 7 have inverses of this type (mod 8) -- Think about mutually prime)

3*3*x = 3*4 (mod 8)

x = 4 mod 8

And the problem is substantially simplified.

Answer 35

ok dude let me copy the messages. Good job in coming up with a problem no1 knows the answer to

Answer 36

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

Answer 37

yup have fun with that I guess.

Answer 38

hey tk, how did you get from
2x=5 (mod 7)
to
2*4 = 1 (mod 7)???

Answer 39

There is no "from" in there.

2x = 5 (mod 7) is the given problem statement

2*4 = 1 (mod 7) is the demonstration that 2 has a multiplicative inverse (mod 7). The inverse is 4.

I then used the multiplicative inverse with the original problem statement.

2x = 5 (mod 7)

4*2*x = 4*5 (mod 7)
Giving
x = 6 (mod 7)

Answer 40

wow is that that hard, or did i miss come questions in between?

Answer 41

oh i see it is two of them
but \(2x\equiv 5(7)\iff 2x\equiv 12(7)\iff x\equiv 6(7)\)

Answer 42

similarly
\[3x\equiv4(8)\iff 3x\equiv 12(8)\iff x\equiv 4(8)\]

Answer 43

2*4 = 1 (mod 7) is the demonstration that 2 has a multiplicative inverse (mod 7). The inverse is 4.

How do you get that? sorry about that just dont really get it

Answer 44

it is clear that \(2\times 4=8\) for sure right? and also that \(8\equiv 1(7)\)

Answer 45

@wednesday09876 this i think is too much work, although you may need it for something later

Answer 46

yeah i got it

Answer 47

so what do i do after that

Answer 48

as @tkhunny was saying now your job is to find \(x\) so that
\[x\equiv 4(\text{ mod }7)\] and also \[x\equiv 4(\text{ mod }8)\]

Answer 49

but how did i legally just get it down to the form where there is one x?

Answer 50

if it was me, i would multiply \(8\times 7\) and then add 4

Answer 51

oh i see what your question is
lets go slow

Answer 52

what ive been trying to understand is how the 2 and 3 disappeared from behind the x

Answer 53

yeah sorry

Answer 54

ok i got it
lets go real slow and get this for sure

Answer 55

you have
\[2x\equiv 5( \text{ mod } 7)\] right

Answer 56

yeah

Answer 57

ok
now forget about this mod for a second
suppose you just had \(2x=5\) what would you do to solve for \(x\)?

Answer 58

divide two over

Answer 59

i assume you mean "divide by 2" and yes, that is what you would do
but you cannot divide this by 2 can you? because you have to work with whole numbers

Answer 60

yeah

Answer 61

so here is what we can do to allow us to divide by 2
add \(7\) to \(5\) because \(5( \text{ mod }7)\equiv 12( \text{ mod }7)\) that should be more or less clear
both 5 and 12 have a remainder of 5 when divided by 7

Answer 62

got it

Answer 63

what i really should have written is that
\[12\equiv 5(\text { mod } 7)\] but no matter i hope you get the idea

Answer 64

so now we have
\[2x\equiv 12 ( \text { mod } 7)\]and now we CAN divide by 2

Answer 65

k?

Answer 66

yeah i got that, but i vaguely recall my teacher saying that when dividing you must divide the mod as well?

Answer 67

divide by \(2\) and we get
\[x\equiv 6( \text { mod } 7)\]

Answer 68

no

Answer 69

alright as long as that is not a rule then yeah i got that part

Answer 70

lets check that this answer is right, so it is not a mystery

Answer 71

suppose \(x=6\)
then \(2x=12\) right? and also \(12\equiv 5(\text { mod }7)\) so we know it is right

Answer 72

aha got it

Answer 73

now lets repeat the process for \(3x\equiv 4(\text { mod }8)\)

Answer 74

you cannot divide 4 by 3, so keep adding 8 until you can

Answer 75

fortunately for you, this requires only one addition
sometimes it takes more

Answer 76

yeah i got it

Answer 77

since \(8+4=12\) is should be clear that
\[12\equiv 4(\text { mod } 8)\] and so now we have
\[3x\equiv 12(\text {mod} 8)\] divide by 4 etc etc

Answer 78

ah thank you

Answer 79

yw

Answer 80

course you still have to solve for \(x\)

Answer 81

yeah i got that part, just needed it simplified so i could do the work

Answer 82

k good

Answer 83

2x = 7m + 5 , m = 0, 1, 2, ...
we want just x so we have to multiply everything by the inverse of 2 mod 7, which is 4.
=> 8x = 7m + 20 => x = 7m + 6

now we sub that in for x in the other congruence =>
3(7m+6) = 21m + 18 = 4 mod 8 => 5m +2 = 4 mod 8
=> 5m = 2 mod 8 again we want only x so we multiply by the inverse of 5 mod 8, which is 5. => 25m = 10 mod 6 => m = 2 mod 8 => m = 8n + 2

now we sub that into our original equation for x...

=> x = 7(8n + 2) + 6 = 56n + 14 + 6 = 56n + 20

so x = 20 mod 56.

I couldn't let it go until i figured it out so i apologize if this is any sort of a nuisance.