How do I solve this Diophantine equation using modulo?

  • Context: MHB 
  • Thread starter Thread starter Petrus
  • Start date Start date
Click For Summary

Discussion Overview

The discussion centers around solving the Diophantine equation $$35y \equiv 13 \mod 97$$. Participants explore various methods for finding solutions, including the use of multiplicative inverses and transformations of the equation. The conversation includes both theoretical approaches and practical calculations.

Discussion Character

  • Exploratory
  • Technical explanation
  • Mathematical reasoning
  • Debate/contested

Main Points Raised

  • One participant rewrites the equation as $$35y = 13 + 97m$$ and derives a general solution $$y = -468 + 97k$$, expressing uncertainty about the next steps.
  • Another participant claims to have found a specific solution $$y = 17$$ by verifying the calculations involving the equation and modulo operations.
  • A third participant discusses the method of finding the multiplicative inverse of 35 modulo 97, concluding that it is 61, leading to the solution $$y \equiv 17 \mod 97$$.
  • One participant expresses confidence in their method but questions whether it is correct, seeking validation from others.
  • Another participant notes the need for more details on how the initial solution $$y = -468 + 97k$$ was derived, indicating a potential gap in the explanation.

Areas of Agreement / Disagreement

There is no consensus on the methods used to solve the equation, as participants present different approaches and calculations. Some participants agree on the solution $$y = 17$$, while others raise questions about the derivation of alternative solutions.

Contextual Notes

Participants express uncertainty regarding the derivation of certain solutions and the correctness of various methods. The discussion reflects differing levels of understanding and approaches to solving Diophantine equations.

Who May Find This Useful

Readers interested in number theory, particularly those studying Diophantine equations and modular arithmetic, may find the various approaches and discussions beneficial.

Petrus
Messages
702
Reaction score
0
Hello MHB,
I have hard understanding what we doing when we solve
$$35y \equiv 13(mod\ 97)$$
I understand we can rewrite that as
$$35y = 13+97m$$
if we replace $$m=-x$$ we got
$$97x+35y=13$$
I get $$gcd(97,35)=1 $$ that means we will have one soloution.
and the diophantine equation got soloution for $$ y=-468+97k
$$ and what shall I do next?

Regards,
 
Mathematics news on Phys.org
Hello MHB,
I finally saw what I did wrong! for people who is interested the soloution will be $$k=5 <=> y=17$$
What have we exactly calculated?
this is what we calculated:
$$35y \equiv 13(mod\ 97)$$
if we $$35*17=595$$ with other words if we take away 13 from 595 and divide by 97 we will get a integer as result so
$$595-13= 582$$ and now to se we get no rest with divide by 97.
$$\frac{582}{97}=6$$ so we solved it correctly!
Regards,
 
Last edited:
Petrus said:
Hello MHB,
I finally saw what I did wrong! for people who is interested the soloution will be $$k=5 <=> y=17$$
What have we exactly calculated?
this is what we calculated:
$$35y \equiv 13(mod\ 97)$$
if we $$35*17=595$$ with other words if we take away 13 from 595 and divide by 97 we will get a integer as result so
$$595-13= 582$$ and now to se we get no rest with divide by 97.
$$\frac{582}{97}=6$$ so we solved it correctly!
Regards,

Given the first order diophantine equation...

$\displaystyle 35 \cdot y \equiv 13\ \text{mod}\ 97$ (1)

... a standard way to solve it is to multiply both members by the multiplicative inverse of 35, if that multiplicative inverse do exists, obtaining...

$\displaystyle y \equiv 35^{-1} \cdot 13\ \text{mod}\ 97$ (2)

If n is prime, then any number mod n different from zero has one and only one multiplicative inverse. In Your case 97 is prime and the multiplicative inverse of 35 is 61 because $\displaystyle 35 \cdot 61 = 2135 = 97 \cdot 22 + 1$, so that the solution is...

$\displaystyle y = 61 \cdot 13 = 793 \equiv 17\ \text{mod}\ 97$ (3)

Kind regards

$\chi$ $\sigma$
 
Hello, Petrus!

Solve: .$$35y \,\equiv\, 13\text{ (mod 97)}$$
We have: .. .35y \:\equiv\:13\text{ (mod 97)}

. . . . . . . . . 35y \:\equiv\:-84\text{ (mod 97)}

Divide by 7: .5y \:\equiv\:-12\text{ (mod 97)}

Then: .5y \:=\:-12 + 97k

Hence: .y \:=\:\frac{97k-12}{5} \:=\:19k-1 + \frac{2k-7}{5}

Since y is an integer, 2k-7 must be a multiple of 5.
This happens when k = 1.Therefore: .y \:=\:19(1) - 1 + \frac{2(1)-7}{5}

. . . . . . . . .y \:=\:17\text{ (mod 97)}
 
chisigma said:
Given the first order diophantine equation...

$\displaystyle 35 \cdot y \equiv 13\ \text{mod}\ 97$ (1)

... a standard way to solve it is to multiply both members by the multiplicative inverse of 35, if that multiplicative inverse do exists, obtaining...

$\displaystyle y \equiv 35^{-1} \cdot 13\ \text{mod}\ 97$ (2)

If n is prime, then any number mod n different from zero has one and only one multiplicative inverse. In Your case 97 is prime and the multiplicative inverse of 35 is 61 because $\displaystyle 35 \cdot 61 = 2135 = 97 \cdot 22 + 1$, so that the solution is...

$\displaystyle y = 61 \cdot 13 = 793 \equiv 17\ \text{mod}\ 97$ (3)

Kind regards

$\chi$ $\sigma$
Hello,
I wounder if it's anything wrong with the way I solve it? I just feel safe with it and I think that is the way we are supposed to solve it, well that is what I did and get correct answer.

Regards,
 
Petrus said:
Hello,
I wounder if it's anything wrong with the way I solve it? I just feel safe with it and I think that is the way we are supposed to solve it, well that is what I did and get correct answer.

Regards,

The great scope of Math is not to solve day by day the occasional problems one meets but to supply instruments to solve specific problems no matter how complex they are. In the modern cryptography diophantine equations similar to one You have proposed but with n a very large prime number are usual and some powerful algorithms for 'fast' discovery of the inverse multiplicative inverse of a number mod n with n very large prime have been found... Kind regards $\chi$ $\sigma$
 
Last edited:
Petrus said:
Hello,
I wounder if it's anything wrong with the way I solve it? I just feel safe with it and I think that is the way we are supposed to solve it, well that is what I did and get correct answer.

Regards,

Hi Petrus, :)

To know whether you solved using a correct method that applies to any Diophantine equation we need some more details. In your post #1, you haven't actually written down how you obtained, \(y=-468+97k\).
 

Similar threads

MHB Solving Diophantine Equation: 97x+35y=13
  • · Replies 24 ·
Replies
24
Views
5K
Undergrad Solving congruences and diophantine equations in number theory
  • · Replies 3 ·
Replies
3
Views
1K
MHB How can we use hints to prove divisibility of Fibonacci numbers?
  • · Replies 1 ·
Replies
1
Views
2K
How should I solve this Diophantine equation word problem?
  • · Replies 4 ·
Replies
4
Views
2K
Undergrad How can I solve diophantine equations effectively?
  • · Replies 10 ·
Replies
10
Views
5K
MHB Solve Polynomial Equation z^6-2z^3+2=0
  • · Replies 11 ·
Replies
11
Views
3K
Solve the simultaneous congruence modulo equation
  • · Replies 3 ·
Replies
3
Views
2K
MHB Understanding Squaring the Bottom of an Equation
  • · Replies 4 ·
Replies
4
Views
2K
MHB Solve the Trigonometry Equation: sin^-1(x) + cos^-1(2x) = π/6
  • · Replies 10 ·
Replies
10
Views
3K
MHB Can't Solve Character Schedule: f(x)=e^x(x^3-2x^2-x+4)-5
  • · Replies 4 ·
Replies
4
Views
3K