How do I solve this Diophantine equation using modulo?

[Petrus]

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

Regards,

 

[Petrus]

Hello MHB,
I finally saw what I did wrong! for people who is interested the soloution will be \(\displaystyle k=5 <=> y=17\)
What have we exactly calculated?
this is what we calculated:
\(\displaystyle 35y \equiv 13(mod\ 97)\)
if we \(\displaystyle 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
\(\displaystyle 595-13= 582\) and now to se we get no rest with divide by 97.
\(\displaystyle \frac{582}{97}=6\) so we solved it correctly!
Regards,

 

[chisigma]

Hello MHB,
I finally saw what I did wrong! for people who is interested the soloution will be \(\displaystyle k=5 <=> y=17\)
What have we exactly calculated?
this is what we calculated:
\(\displaystyle 35y \equiv 13(mod\ 97)\)
if we \(\displaystyle 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
\(\displaystyle 595-13= 582\) and now to se we get no rest with divide by 97.
\(\displaystyle \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$

 

[soroban]

Hello, Petrus!

Solve: .\(\displaystyle 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)}$$

 

[Petrus]

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,

 

[chisigma]

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$

 

[Sudharaka]

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