mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2018-04-28, 01:33   #1
MARTHA
 
Jan 2018

43 Posts
Default Let 6x+5=10y+7=15z+2;can these integers be calculated directly without brute force..

Let 6x+5=10y+7=15z+2; the value of x,y,z would be 2,1,1 for integer solution..
can these integers be calculated directly without brute force..
MARTHA is offline   Reply With Quote
Old 2018-04-28, 01:48   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts
Default

Quote:
Originally Posted by MARTHA View Post
Let 6x+5=10y+7=15z+2; the value of x,y,z would be 2,1,1 for integer solution..
can these integers be calculated directly without brute force..
x is 2 mod 5, y is 1 mod 3,z is 1 mod 2 okay , I suck at algebraic manipulations.

Last fiddled with by science_man_88 on 2018-04-28 at 01:50
science_man_88 is offline   Reply With Quote
Old 2018-04-28, 01:52   #3
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

22·3·179 Posts
Default

I think you will have to try integer values for x and y to find an integer z.

https://www.wolframalpha.com/input/?...%2B7%3D15z%2B2

https://www.wolframalpha.com/input/?...er+the+integer
a1call is online now   Reply With Quote
Old 2018-04-28, 04:10   #4
axn
 
axn's Avatar
 
Jun 2003

3·5·73 Posts
Default

Let N=6x+5=10y+7=15z+2. We can setup the following system of modular equations.

N=5 (mod 6)
N=7 (mod 10)
N=2 (mod 15)

We can't solve this directly via Chinese Remainder Theorem since 6,10, and 15 are not pairwise coprime. Let's break them up into prime factors

From first:
N==1 (mod 2)
N==2 (mod 3)

From second:
N==1 (mod 2)
N==2 (mod 5)

From third:
N==2 (mod 3)
N==2 (mod 5)

Phew! No inconsistencies here. No we can solve this system using CRT
N==1 (mod 2)
N==2 (mod 3)
N==2 (mod 5)
axn is offline   Reply With Quote
Old 2018-04-28, 04:39   #5
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

C6716 Posts
Default

So the solution becomes:

N=30k+17

and

x=5k+2
y=3k+1
z=2k+1

for k=0,1,2,3,...

Last fiddled with by ATH on 2018-04-28 at 04:43
ATH is offline   Reply With Quote
Old 2018-04-28, 13:12   #6
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

115538 Posts
Default

A standard test for consistency of linear congruences

N == a (mod M1) and
N == b (mod M2)

when the moduli are not pairwise relatively prime is,

gcd(M1, M 2) divides a - b.

The congruences in question here are

N == 5 (mod 6)
N == 7 (mod 10)
N == 2 (mod 15)

Here, gcd(6, 10) = 2, and 2 divides 5 - 7 = -2; gcd(6, 15) = 3, and 3 divides 5 - 2 = 3; finally, gcd(10,15) = 5 and 5 divides 7 - 2 = 5.

This shows up as redundancies when the congruences are expressed as congruences to pairwise relatively prime moduli.

Given two congruences

N == a (mod M1) and N == b (mod M2)

with gcd(M1, M2) = 1, a solution may be found if we can find X and Y with

X == 1 (mod M1), X == 0 (mod M2), and

Y == 0 (mod M1), Y == 1 (mod M2).

Then, N = a*X + b*Y solves the two congruences simultaneously.

Now, X = r*M2 = s*M1 + 1, so r*M2 - s*M1 = 1. Similarly, Y = p*M1 = q*M2 + 1, so that p*M1 - q*M2 = 1.

These r, s, p, and q may be found using the Euclidean algorithm for gcd(M1, M2).

Showing that this works when gcd(M1, M2) divides a - b is left as an exercise for the reader
;-)

Last fiddled with by Dr Sardonicus on 2018-04-28 at 13:16 Reason: Fixing awkward phrasing
Dr Sardonicus is offline   Reply With Quote
Old 2018-04-28, 15:01   #7
MARTHA
 
Jan 2018

43 Posts
Smile Thank you all !!!

I got more answers than was expecting..
thanks a ton everyone
MARTHA is offline   Reply With Quote
Old 2018-04-28, 15:05   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by a1call View Post
I think you will have to try integer values for x and y to find an integer z.

https://www.wolframalpha.com/input/?...%2B7%3D15z%2B2

https://www.wolframalpha.com/input/?...er+the+integer
Mod 5 it becomes x=2=2; not much choosing there. Lcm(6,10,15)=30 so once you find one solution you can find infinitely many more.

Last fiddled with by science_man_88 on 2018-04-28 at 15:07
science_man_88 is offline   Reply With Quote
Old 2018-04-29, 05:43   #9
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

Yet another answer, in PARI/GP:
Code:
chinese([Mod(5,6),Mod(7,10),Mod(2,15)])
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Let y^2=xz-x^2+1, and if value of x is known, can y and z be directly calculated? Given all variable MARTHA Number Theory Discussion Group 11 2018-03-02 15:55
How are GHz-Days calculated? Unregistered Information & Answers 10 2013-05-17 14:26
Any open problems out there where a brute force attack would help, but no DC program? jasong Math 21 2012-02-13 16:05
how is the throughput calculated? ixfd64 PrimeNet 5 2008-05-21 13:39
Curious how sieve points are calculated VJS Prime Sierpinski Project 9 2006-09-10 19:02

All times are UTC. The time now is 08:14.


Mon Oct 18 08:14:05 UTC 2021 up 87 days, 2:43, 0 users, load averages: 1.43, 1.16, 1.05

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.