Are There Multiple Solutions to this System of Linear Congruences?

  • Context: Undergrad 
  • Thread starter Thread starter oliver$
  • Start date Start date
  • Tags Tags
    Linear System
Click For Summary

Discussion Overview

The discussion revolves around a system of linear congruences and whether multiple solutions exist for the given equations. Participants explore the implications of solving these equations under modular arithmetic, specifically modulo 35, 7, and 5.

Discussion Character

  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant presents a system of equations and claims to find a solution, questioning the uniqueness of that solution.
  • Another participant argues that with two equations and two unknowns, a unique solution should exist unless the equations are dependent or the variables are of different types.
  • There is a suggestion to verify the solution by substituting back into the original equations.
  • One participant prompts further reflection on the conditions for multiple solutions and suggests considering the equations modulo 7 and 5 to apply linear algebra concepts.
  • A participant acknowledges a mistake in their previous solution for y and suggests working with smaller moduli for clarity.
  • Another participant shares their findings after working with mod 7 and mod 5, presenting potential solutions and questioning whether to apply the Chinese Remainder Theorem (CRT).
  • There is a correction regarding the mod 5 solution, indicating a need for further verification.

Areas of Agreement / Disagreement

Participants express differing views on the existence of multiple solutions, with some asserting uniqueness based on the number of equations and others suggesting the possibility of more solutions depending on the modular context.

Contextual Notes

Participants note the importance of checking solutions and the potential for errors in calculations, particularly when working with modular arithmetic. The discussion highlights the complexity of solving systems of linear congruences and the need for careful consideration of modular properties.

Who May Find This Useful

This discussion may be useful for individuals interested in modular arithmetic, systems of equations, and the application of the Chinese Remainder Theorem in mathematical problem-solving.

oliver$
Messages
6
Reaction score
0
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?
 
Physics news on Phys.org
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:
You might want to check your solution by substituting it back into the original equations.
 
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)
 
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:
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?
 
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).
 
sorry, i meant (2,1).
 

Similar threads

High School What unique contributions to math did linear algebra make?
  • · Replies 19 ·
Replies
19
Views
4K
Find the solutions of the system of congruences
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Solving a complex linear system with parameters
  • · Replies 11 ·
Replies
11
Views
2K
Graduate Finding operators (and, possibly, exponents) in a system
  • · Replies 2 ·
Replies
2
Views
2K
Graduate Chinese Remainder Theorem, Solving For Multiplicative Inverses
  • · Replies 2 ·
Replies
2
Views
6K
Solving Diophantine Equations Using CRT
  • · Replies 2 ·
Replies
2
Views
2K
Finding the Inverse Integer Modulo n
  • · Replies 4 ·
Replies
4
Views
3K
Find the solutions of the following system of congruences
  • · Replies 2 ·
Replies
2
Views
1K
MHB Basis for set of solutions for linear equation
  • · Replies 6 ·
Replies
6
Views
2K
High School Why is there a solution to this system?
  • · Replies 15 ·
Replies
15
Views
2K