System of linear congruences

  • Thread starter oliver$
  • Start date
  • #1
6
0

Main Question or Discussion Point

the system:

24x + 11y= 4 (mod 35)
5x + 7y= -13 (mod 35)

is solved to get:

-113y= 111 (mod 35)
113x= 171 (mod 35)

which gives: (17,8).

should there not be more solutions?
 

Answers and Replies

  • #2
1,056
0
No, with two unknowns, x and y, we need exactly two linear equations to find the unique solution. Now, if x or y was quadratic, it would be different.

You can see from your own work that, we use one of the equations to eliminate one of the terms. Thus what remains is all in one unknown.

However, since it is a modulo equation, you can add or subtract any multiple of 35 to x or y.
 
Last edited:
  • #3
shmoe
Science Advisor
Homework Helper
1,992
1
You might want to check your solution by substituting it back into the original equations.
 
  • #4
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
Ask yourself two questions:

(1) Why do you think there should be more solutions?
(2) What things do you know about solutions to systems of linear equations?

When answering these questions, it might help to consider things mod 7 and mod 5, so that you're working over a field (and thus most of what you learned in linear algebra is applicable)
 
  • #5
1,056
0
Oliver$: should there not be more solutions?

Unfortunately "Yes," since there is a mistake in your value for y.

It might be easier as Hurkyl suggests to work with modulo 5 and modulo 7.
 
Last edited:
  • #6
14
0
ok, upon doing it (mod 7) and (mod 5), i got (3,4) (mod 7) and (1,2) (mod 7). does that sit well? or should i now apply the CRT?
 
  • #7
shmoe
Science Advisor
Homework Helper
1,992
1
ascheras said:
ok, upon doing it (mod 7) and (mod 5), i got (3,4) (mod 7) and (1,2) (mod 7). does that sit well? or should i now apply the CRT?
You can use the CRT after, but you might want to check your (1,2) answer mod 5 (I assume that's your mod 5 solution).
 
  • #8
14
0
sorry, i meant (2,1).
 

Related Threads on System of linear congruences

Replies
4
Views
2K
Replies
1
Views
4K
  • Last Post
Replies
3
Views
2K
Replies
3
Views
9K
  • Last Post
Replies
23
Views
4K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
3
Views
4K
  • Last Post
Replies
1
Views
2K
Top