Question

What exactly is a mutually incongruent solution of a congruence? Can you give an example?

Answer 1

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

Answer 2

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

Answer 3

incongruent is just an opposite of congruent

Answer 4

ok, so two numbers m and n are mutually incongruent mod c means

m not congruent n (mod c)

Answer 5

Yep!

Answer 6

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

Answer 7

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

Answer 8

the answer should be just \(\{7\}\)

Answer 9

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

Answer 10

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

Answer 11

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

Answer 12

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?

Answer 13

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.

Answer 14

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

Answer 15

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

Answer 16

looks good

Answer 17

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

Answer 18

because gcd(9,15) = 3 | 12

Answer 19

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

Answer 20

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

Answer 21

consider below congruence :
\[9x\equiv 2\pmod{15}\]

how many solutions ?

Answer 22

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

Answer 23

right?

Answer 24

Yep!

Answer 25

so.....???

Answer 26

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

Answer 27

what are the mutually incongruent solutions?

Answer 28

let k = 0,1,2

Answer 29

the incongruent solutions are \(\{3,8,13\}\)

they are mutually incongruent in mod \(15\)

Answer 30

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

Answer 31

they are the most convenient ones

Answer 32

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

Answer 33

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

Answer 34

3 and 18 are not incongruent

Answer 35

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

Answer 36

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

Answer 37

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

Answer 38

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

Answer 39

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

Answer 40

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

Answer 41

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

Answer 42

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?

Answer 43

mod 15 btw

Answer 44

{3, 8, 13} right

Answer 45

opps yeah. Typo :D

Answer 46

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

Answer 47

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

in mod 15

Answer 48

notice i have changed 5k to 15k

Answer 49

3 + 5k refers to mod 5

3 + 15k refers to mod 15

Answer 50

I think I understand it better now although I still need to do some examples to clear up any confusion.

@ganeshie8 thank you :)

Answer 51

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\}\)

Answer 52

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

Answer 53

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 }

Answer 54

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

Answer 55

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

Answer 56

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

Answer 57

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

Answer 58

awesome. Thanks