How to solve these equations

mr.wong · 2016-12-11 17:45:00

For equations of the form 182 * i - 165 * j = p
where i and j are integers and p is prime .
( 182 = 2*7*13 while 165 = 3*5*11 . )
i is relatively prime with 165 and j while j is relatively prime
with 182 and i . Solve i and j for
(1) 182 * i - 165 * j = 89
(2) 182 * i - 165 * j = 241
(3) 182 * i - 165 * j = 419
(4) 182 * i - 165 * j = 571
(5) 182 * i - 165 * j = 929
(6) 182 * i - 165 * j = 997

zetafunc · 2016-12-11 20:08:02

Try reducing each equation modulo the prime factors of 182 and 165.

thickhead · 2016-12-11 20:55:54

182-165=17 ........................(1)
If we multiply both sides by 10 (to get R.H.S.>165) 10(182-165)=170=1*165+5 which gives us
10*182-11*165=5 ..................(2)
If we can make R.H.S of the required equation as linear combination of (1) and (2) we get the solution.
(1) Since 89=2*17+11*5
2*(182-165)+11(10*182-11*165)=89 which leads to
182*112-165*123=89. which givesi=112 and j=123.
However this is not unique combination. i=112+165n and j=123+182n will also foot the bill.
I am aware that this may not work out in cases where linear combination of 17 and 5 may not be possible.But still I am sure some more relations like (2) could be formed which will help linear combination.

mr.wong,
It is o.k. I found the answer for any number on R.H.S.
1=3*17-10*5=3*{182-165}-10*{10*182-11*165}=182*(-97)+165*107 i=-97 and j=-107
e.g.(5) could be written
182*{-97*929}-165*{-107*929}=929
i=-97*929 and j=-107*929

Last edited by thickhead (2016-12-12 02:47:28)

mr.wong · 2016-12-12 17:22:17

Hi zetafunc ,

Thanks for your opinion !

Hi thickhead ,

Thanks much for your reply !
Originally I wonder why I can't get the 6 primes from (1) to (6) using the
expression 182 * i - 165 * j , now I have found that it's because I omitted
i for 53 after (108) at the algorithm .
As 182 * 53 = 9646 - 165 * 55 = 9075 ⇒ d = 571 (P) for i=53 and j=55
Let 182 * i - 165 * j = -571 ⇒ 182 ( 53 + i ) - 165 ( 55 + j ) = 0
⇒ 182 ( 53 + i ) =165 ( 55 + j ) ⇒ i = 165 - 53 = 112 and j = 182 - 55 = 127
Thus the prime -571 will occur in its symmetric place with i = 112 and j = 127 .

However , the method at shown in # 3 seems not work since i and j should be
relatively prime .

Last edited by mr.wong (2016-12-13 23:21:33)

thickhead · 2016-12-12 18:26:21

mr.wong,
I am very sorry,I had not read the problem carefully. 182 and 165 are relatively prime but I had overlooked that for i and j. I was wondering why there are only some specific numbers on R.H.S.As a matter of fact I had not gone through your earlier thread on prime numbers.

thickhead · 2016-12-12 20:40:43

(5)182*{967}-165*{1061}=929
Is it o.k.?

mr.wong · 2016-12-13 16:31:41

Hi thickhead ,

Your answer is correct but the values i = 967 and j = 1061 are too large .
I have got an answer for i = 142 and j = 151 .
By the method you stated in # 3 , I tried 929 = a * 17 + b * 5 and got
929 = 2 * 17 + 179 * 5 ( by trial and error ) , thus
929 = 2 * (182 - 165 ) + 179 * ( 10 * 182 - 11 * 165 )
= 2 * 182 + 179 * 10 * 182 - ( 2 * 165 + 179 * 11 * 165 )
= 1792 * 182 - 1971 * 165
Thus an answer is i = 1792 and j = 1971 .
Since 1792 = 10 * 165 + 142 while 1971 = 10 * 182 + 151 ,
thus 929 = ( 10 * 165 + 142 ) * 182 - ( 10 * 182 + 151 ) * 165
= 10 * 165 * 182 + 142 * 182 - ( 10 * 182 * 165 + 151 * 165 )
= 142 * 182 - 151 * 165
Thus another answer is i = 142 and j = 151
Your answer can also be simplified as 967 = 5 * 165 + 142 while
1061 = 5 * 182 + 151 .

thickhead · 2016-12-13 17:44:23

When I got this 182*{-97*929}-165*{-107*929}=929 I was not happy since i and j were negative but since your condition was on integer I allowed it.However it is possible to add and subtract packets of 182*165 as many as you like to make them positive keeping eye on relatively prime condition. I added and subtracted 552(547 is sufficient to make them positive but relatively prime condition could not be met) packets to each term.Thus 182*{-97*929+552*165}=967 and 165*{-107*929+552*182}=1061. as I told you I relied on only (1) and (2) in #3 but more such relations could be found.

Last edited by thickhead (2016-12-13 18:17:56)

zetafunc · 2016-12-13 20:48:16

If you reduce each equation modulo the prime factors of 182, 165, then you'll obtain a bunch of simultaneous congruences which you can find all the possible solutions (i,j) to using the Chinese remainder theorem.

thickhead · 2016-12-13 21:21:55

mr.wong,
I goofed about the restraints again.On close observation I find i is relatively prime with 165 only ,not necessarily with 182. So
182*{-97*929+547*165}=142 and 165*{-107*929+547*182}=151
182*{-97*929+548*165}=307and 165*{-107*929+548*182}=333
182*{-97*929+549*165}=472 and 165*{-107*929+549*182}=515
182*{-97*929+550*165}=637 and 165*{-107*929+550*182}=697
182*{-97*929+551*165}=802 and 165*{-107*929+551*182}=879
All these are valid pairs of i and j.

mr.wong · 2016-12-13 23:08:52

Hi zetafunc ,

Will you please give an example ?

Hi thickhead ,

Once you have got a valid pair of i and j , then you may add
n * 182 * 165 to both sides of 182 * i and 165 * j and obtain a bunch of i and j as you had stated in # 3 . While to express a certain prime as a * 17 + b * 5 may need trial and error .

zetafunc · 2016-12-16 22:04:17

Similarly This yields the set However, we still need to deal with the conditions you've imposed on which are that:

The first two are trivially true (i is never 0 modulo 165, j is never 0 modulo 182). It remains to exclude the cases where (i,j) = 1. That is, we need to exclude any n such that:

These have solutions and So the solution set is:

The other questions are done in the same way.

Last edited by zetafunc (2016-12-17 05:17:21)

zetafunc · 2016-12-16 22:05:19

mr.wong wrote:

While to express a certain prime as a * 17 + b * 5 may need trial and error .

Bezout's identity

bobbym · 2016-12-17 04:31:20

Hi zetafunc;

For an ordinary ax-by=c we could hunt for one answer and then use Bezouts to get as many as we need. But, and this is a big but, he has extra conditions on his ax-by=c. That might matter and might not. What do you think?

zetafunc · 2016-12-17 04:48:56

What are the extra conditions?

bobbym · 2016-12-17 04:52:09

i is relatively prime with 165 and j while j is relatively prime
with 182 and i

When I read that it began to sound more like a computer problem than a math one.

zetafunc · 2016-12-17 05:02:06

I was referring to this part of post #11:

mr.wong wrote:

While to express a certain prime as a * 17 + b * 5 may need trial and error .

which, as you say, can be done via Bezout's. Also, i is always coprime to 165, and j is always coprime to 182 in the set in post #12. The only issue is the condition (i,j) = 1.

Last edited by zetafunc (2016-12-17 05:33:03)

bobbym · 2016-12-17 05:04:42

you would need to exclude those cases from the solution set given in post #12.

That will require what I call unmathlike moves. You have to pick them out manually or by computer.

zetafunc · 2016-12-17 05:07:56

Made an edit to post #17.

So the only condition which remains is i being coprime to j. A start would be to solve the congruences:

and You can then exclude any such no?

bobbym · 2016-12-17 05:11:40

Those could be solved using M.

zetafunc · 2016-12-17 05:16:01

M gave me the solutions (I made an edit to post #12 in light of the new information about the conditions he wants to impose on i,j).

bobbym · 2016-12-17 05:18:38

Oh okay, I am looking at it now.

I would have used the Solve command with a modulo option. What did you do?

zetafunc · 2016-12-17 05:20:44

I used Wolfram Alpha to save time, although that works too.

bobbym · 2016-12-17 05:24:59

Okay, then he has already enough to complete his question.

mr.wong · 2016-12-17 16:37:51

Hi zetafunc ,

Thanks much for your reply ! But I really not quite understand your work since I have never learnt maths on congruence before . Luckily this does not affect my work on the algorithm of primes as I had tried various values of i and j one by one to obtain various primes . Now all the 6 equations have been solved . ( Previously I had made mistakes for omitting certain values of
i and j . )

Hi bobbym ,

Thanks for your participation on discussion of the question !

Math Is Fun Forum

#1 2016-12-11 17:45:00

How to solve these equations

#2 2016-12-11 20:08:02

Re: How to solve these equations

#3 2016-12-11 20:55:54

Re: How to solve these equations

#4 2016-12-12 17:22:17

Re: How to solve these equations

#5 2016-12-12 18:26:21

Re: How to solve these equations

#6 2016-12-12 20:40:43

Re: How to solve these equations

#7 2016-12-13 16:31:41

Re: How to solve these equations

#8 2016-12-13 17:44:23

Re: How to solve these equations

#9 2016-12-13 20:48:16

Re: How to solve these equations

#10 2016-12-13 21:21:55

Re: How to solve these equations

#11 2016-12-13 23:08:52

Re: How to solve these equations

#12 2016-12-16 22:04:17

Re: How to solve these equations

#13 2016-12-16 22:05:19

Re: How to solve these equations

#14 2016-12-17 04:31:20

Re: How to solve these equations

#15 2016-12-17 04:48:56

Re: How to solve these equations

#16 2016-12-17 04:52:09

Re: How to solve these equations

#17 2016-12-17 05:02:06

Re: How to solve these equations

#18 2016-12-17 05:04:42

Re: How to solve these equations

#19 2016-12-17 05:07:56

Re: How to solve these equations

#20 2016-12-17 05:11:40

Re: How to solve these equations

#21 2016-12-17 05:16:01

Re: How to solve these equations

#22 2016-12-17 05:18:38

Re: How to solve these equations

#23 2016-12-17 05:20:44

Re: How to solve these equations

#24 2016-12-17 05:24:59

Re: How to solve these equations

#25 2016-12-17 16:37:51

Re: How to solve these equations

Board footer