## wednesday09876 Group Title FAN AND MEDAL WILL BE REWARDED: Solve this system of congruences 2x=5 (mod 7) 3x=4 (mod 8) 11 months ago 11 months ago

1. wednesday09876 Group Title

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

2. pgpilot326 Group Title

not sure how to explain but I got an answer for the first, x must be equivalent to 6 + 7k, k = 0,1,2,...

3. wednesday09876 Group Title

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

4. pgpilot326 Group Title

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

5. jefftheloveableguy Group Title

x is 5

6. jefftheloveableguy Group Title

lol just learned it online

7. jefftheloveableguy Group Title

need explanation?

8. pgpilot326 Group Title

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

9. wednesday09876 Group Title

where do we get 3 mod 7 though?

10. wednesday09876 Group Title

jeff, yeah thanks that would be great.

11. jefftheloveableguy Group Title
12. pgpilot326 Group Title

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

13. jefftheloveableguy Group Title

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

14. jefftheloveableguy Group Title

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

15. wednesday09876 Group Title

alright just one sec im gonna try some work real quick

16. jefftheloveableguy Group Title

ok 5 doesn't work haha

17. jefftheloveableguy Group Title

40 does nice job

18. wednesday09876 Group Title

19. wednesday09876 Group Title

because i cant really solve further than that

20. jefftheloveableguy Group Title

21. wednesday09876 Group Title

alright thanks

22. tkhunny Group Title

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)

23. pgpilot326 Group Title

have a look

24. wednesday09876 Group Title

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

25. jefftheloveableguy Group Title

26. jefftheloveableguy Group Title

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

27. wednesday09876 Group Title

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

28. wednesday09876 Group Title

do you think you could like copy the messages??

29. jefftheloveableguy Group Title

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

30. wednesday09876 Group Title

haha nvm then thanks

31. jefftheloveableguy Group Title

wed. what class is this for?

32. wednesday09876 Group Title

algebra 2 trig

33. jefftheloveableguy Group Title

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

34. tkhunny Group Title

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.

35. jefftheloveableguy Group Title

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

36. jefftheloveableguy Group Title

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

37. jefftheloveableguy Group Title

yup have fun with that I guess.

38. wednesday09876 Group Title

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

39. tkhunny Group Title

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)

40. satellite73 Group Title

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

41. satellite73 Group Title

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

42. satellite73 Group Title

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

43. wednesday09876 Group Title

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

44. satellite73 Group Title

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

45. satellite73 Group Title

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

46. wednesday09876 Group Title

yeah i got it

47. wednesday09876 Group Title

so what do i do after that

48. satellite73 Group Title

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)$

49. wednesday09876 Group Title

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

50. satellite73 Group Title

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

51. satellite73 Group Title

oh i see what your question is lets go slow

52. wednesday09876 Group Title

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

53. wednesday09876 Group Title

yeah sorry

54. satellite73 Group Title

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

55. satellite73 Group Title

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

56. wednesday09876 Group Title

yeah

57. satellite73 Group Title

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

58. wednesday09876 Group Title

divide two over

59. satellite73 Group Title

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

60. wednesday09876 Group Title

yeah

61. satellite73 Group Title

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

62. wednesday09876 Group Title

got it

63. satellite73 Group Title

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

64. satellite73 Group Title

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

65. satellite73 Group Title

k?

66. wednesday09876 Group Title

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

67. satellite73 Group Title

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

68. satellite73 Group Title

no

69. wednesday09876 Group Title

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

70. satellite73 Group Title

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

71. satellite73 Group Title

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

72. wednesday09876 Group Title

aha got it

73. satellite73 Group Title

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

74. satellite73 Group Title

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

75. satellite73 Group Title

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

76. wednesday09876 Group Title

yeah i got it

77. satellite73 Group Title

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

78. wednesday09876 Group Title

ah thank you

79. satellite73 Group Title

yw

80. satellite73 Group Title

course you still have to solve for $$x$$

81. wednesday09876 Group Title

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

82. satellite73 Group Title

k good

83. pgpilot326 Group Title

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.