## anonymous one year ago What exactly is a mutually incongruent solution of a congruence? Can you give an example?

1. ganeshie8

$$1$$ and $$6$$ are not mutually incongruent in mod $$5$$ because $$1\equiv 6\pmod{5}$$

2. ganeshie8

$$1$$ and $$3$$ are mutually incongruent in mod $$5$$ because $$1\not\equiv 3\pmod{5}$$

3. ganeshie8

incongruent is just an opposite of congruent

4. anonymous

ok, so two numbers m and n are mutually incongruent mod c means m not congruent n (mod c)

5. ganeshie8

Yep!

6. anonymous

For this example: Find a complete set of mutually incongruent solutions of 7x≡5 (mod 11)

7. anonymous

x = 7, so all solutions are x = 7 + 11k, k an integer

8. ganeshie8

the answer should be just $$\{7\}$$

9. anonymous

why {7} ? and not, say {18} ??

10. ganeshie8

sure, you can put any single integer that is congruent to 7

11. ganeshie8

but the numbers 0 to n-1 are more convenient and look better

12. anonymous

But how does the number 7 or any number congruent to 7 mod 11 capture the idea of "mutually incongruent" solution? if 7 not congruent m (mod 11), what numbers play in the role of m according to the definition of mutually incongruent?

13. ganeshie8

there are no other integer solutions, it is like asking for all the mutually perpendicular vectors that are solutions, if there is only one vector, you give only that.

14. ganeshie8

every other solution is congruent to 7, so there are no other incongruent solutions

15. anonymous

huhm... ok, let me give another example where it has more than 1 mutually incongruent solution. 9x ≡ 12 (mod 15). Since gcd(9,15) = 3, there will be 3 mutually incongruent solutions

16. ganeshie8

looks good

17. ganeshie8

no wait, how do you know there exists a solution ?

18. anonymous

because gcd(9,15) = 3 | 12

19. anonymous

I see x = 3 is one of the solution so all solution is x = 3 + k * 15/gcd(9,15) x = 3 + 5k

20. ganeshie8

"If a solution exists", then there will be exactly 3 incongruent solutions

21. ganeshie8

consider below congruence : $9x\equiv 2\pmod{15}$ how many solutions ?

22. anonymous

none, gcd(9,15) does not divide 2

23. anonymous

right?

24. ganeshie8

Yep!

25. anonymous

so.....???

26. anonymous

let's get back to 9x ≡ 12 (mod 15). There will be exactly 3 mutually incongruent solutions. And all solutions are x = 3 + 5k

27. anonymous

what are the mutually incongruent solutions?

28. ganeshie8

let k = 0,1,2

29. ganeshie8

the incongruent solutions are $$\{3,8,13\}$$ they are mutually incongruent in mod $$15$$

30. anonymous

how do you know to let k = 0,1,2??

31. ganeshie8

they are the most convenient ones

32. ganeshie8

letting k = 222, 223,224 is technically fine but you're not keeping things simple here

33. anonymous

ok, let 0 <= <= 10, then x = 3,8,13, 18, 23, 28, 33, 38, 43, 48, 53

34. ganeshie8

3 and 18 are not incongruent

35. anonymous

right. I was trying to understand how to find the incongruent solutions by listing a few solutions

36. anonymous

what i notice is 3 + 15 = 18 8 + 15 = 23 13 + 15 = 28

37. anonymous

it's somehow like {3,8,15}, {18,23,28}

38. ganeshie8

notice that any integer greater than or equal to 15 is congruent to some integer in the set $$\{0,1,2,\ldots,14\}$$

39. ganeshie8

so we don't need to bother about anything greater than 14

40. ganeshie8

and we don't need to bother about anything less than 0

41. ganeshie8

the set of residues $$\{0, 1, 2, \ldots, n-1\}$$ is our most favorite one, when somebody asks you for incongruent solutions, they expect you to give them from this set

42. anonymous

So {3,8,15} are the set of mutually incongruent because 3 + 5k not congruent 8 + 5s not congruent 15 + 5t, for all integer k,s,t Is this what the incongruent solutions really mean?

43. anonymous

mod 15 btw

44. ganeshie8

{3, 8, 13} right

45. anonymous

opps yeah. Typo :D

46. anonymous

3 + 5k not congruent 8 + 5s not congruent 13 + 5t (mod 15), for all integer k,s,t

47. ganeshie8

3 + 15k not congruent 8 + 15s not congruent 13 + 15t, for all integer k,s,t in mod 15

48. ganeshie8

notice i have changed 5k to 15k

49. ganeshie8

3 + 5k refers to mod 5 3 + 15k refers to mod 15

50. anonymous

I think I understand it better now although I still need to do some examples to clear up any confusion. @ganeshie8 thank you :)

51. ganeshie8

basically we're "lifting" the solutions from mod5 to mod15, so $$x\equiv 3\pmod{5}$$ gives 3 incongruent solutions in mod 15 : $$\{3,8,13\}$$

52. anonymous

yeah, that's what I noticed earlier when I said 3 + 15 = 18 8 + 15 = 23 13 + 15 = 28

53. anonymous

so instead of expressing all solutions in the form of 3 + 5k, we can express all solutions in terms of mutually incongruent soltuions. I.e {x | x = 3 + 15k or x = 8 + 15k or x = 13 + 15k }

54. ganeshie8

you may simply say, the solutions are $$x\equiv 3\pmod{5}$$

55. ganeshie8

you could also say $$x\equiv 3,8,13\pmod{15}$$

56. anonymous

right right. That's exactly what I was trying to say :D

57. ganeshie8

if you're not explicitly asked for the form of solutions, leaving it as $$x\equiv 3\pmod{5}$$ looks neat

58. anonymous

awesome. Thanks