Solve the congruence to the smallest possible modulus.

  • Thread starter sg001
  • Start date
  • Tags
    Modulus
In summary, to solve the congruence 38x\equiv10 (mod84) to the smallest possible modulus, we need to use the GCD algorithm to switch the equation around and simplify it. By using this approach, we can find the values of x and y, and ultimately solve the congruence.
  • #1
sg001
134
0

Homework Statement



solve the congruence to the smallest possible modulus.

38x[itex]\equiv[/itex]10 (mod84)



Homework Equations





The Attempt at a Solution



Ok so I thought I knew how to do these but apparently not.

So I start out by

38x+84y = 10

Now I think I should find the gcd so I can simplify

so

84 = 38(2) + 8[itex]\Rightarrow[/itex] 8= 84 - 38(2)

38= 8(4) + 6 [itex]\Rightarrow[/itex] 6= 38 - 8(4)

8 = 6(1) + 2 [itex]\Rightarrow[/itex] 2 = 8 - 6(1)

6 = 2(3) + 0 [itex]\Leftrightarrow[/itex] gcd = 2

so 19x + 42y = 5


but then where? I seem to get lost at this point?
 
Physics news on Phys.org
  • #2
You need to use GCD algorithm, but not just to find GCD. It's a more powerful tool. Let me demonstrate.

Lets start with your simplified version, 19x=5 (mod42), which you turn into 19x+42y=5. But if you know x, you know y. If you know y, you know x. So we can switch things around.

42y=5 (mod19)

Except 42>19, and we can take 19 away twice.

4y=5 (mod19)

Better! But why should we stop?

4y+19z=5

19z=5 (mod4)

3z=5 (mod4)

3z+4w=5

4w=5 (mod3)

w=5

Woo-hoo! Now, you can use w to find z, z to find y... I'll let you do all that.
 
  • #3
K^2 said:
You need to use GCD algorithm, but not just to find GCD. It's a more powerful tool. Let me demonstrate.

Lets start with your simplified version, 19x=5 (mod42), which you turn into 19x+42y=5. But if you know x, you know y. If you know y, you know x. So we can switch things around.

42y=5 (mod19)

Except 42>19, and we can take 19 away twice.

4y=5 (mod19)

Better! But why should we stop?

4y+19z=5

19z=5 (mod4)

3z=5 (mod4)

3z+4w=5

4w=5 (mod3)

w=5

Woo-hoo! Now, you can use w to find z, z to find y... I'll let you do all that.

ok good got it now thanks.
 

1. What is a congruence?

A congruence is a mathematical concept that describes the relationship between two numbers or objects that have the same remainder when divided by a given number. It is denoted by the symbol ≡ and is read as "congruent to."

2. How do you solve a congruence?

To solve a congruence, you need to find the value of the unknown number or variable that satisfies the given congruence statement. This is typically done by using basic algebraic operations such as addition, subtraction, multiplication, and division.

3. What is the smallest possible modulus?

The modulus in a congruence statement is the number that is being divided by to determine the remainder. The smallest possible modulus is the smallest number that can be used to divide both numbers in the congruence statement without resulting in a remainder. It is usually denoted by the letter m.

4. How do you determine the smallest possible modulus?

To determine the smallest possible modulus, you need to find the greatest common divisor (GCD) of the two numbers in the congruence statement. The GCD is the largest number that divides both numbers without resulting in a remainder. The smallest possible modulus is then the GCD of the two numbers.

5. Why is it important to solve a congruence to the smallest possible modulus?

Solving a congruence to the smallest possible modulus allows for the most simplified solution and eliminates the possibility of extraneous solutions. It also helps to reduce the complexity of the congruence and makes it easier to work with in further calculations.

Similar threads

  • Calculus and Beyond Homework Help
Replies
6
Views
955
  • Calculus and Beyond Homework Help
Replies
4
Views
2K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
667
  • Calculus and Beyond Homework Help
Replies
2
Views
969
  • Calculus and Beyond Homework Help
Replies
1
Views
5K
Replies
5
Views
979
  • Calculus and Beyond Homework Help
Replies
15
Views
1K
  • Calculus and Beyond Homework Help
Replies
7
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
Back
Top