 mersenneforum.org > Math Let 6x+5=10y+7=15z+2;can these integers be calculated directly without brute force..
 Register FAQ Search Today's Posts Mark Forums Read 2018-04-28, 01:33 #1 MARTHA   Jan 2018 43 Posts 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..   2018-04-28, 01:48   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts Quote:
 Originally Posted by MARTHA 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   2018-04-28, 01:52 #3 a1call   "Rashid Naimi" Oct 2015 Remote to Here/There 22·3·179 Posts 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   2018-04-28, 04:10 #4 axn   Jun 2003 3·5·73 Posts 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)   2018-04-28, 04:39 #5 ATH Einyen   Dec 2003 Denmark C6716 Posts 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   2018-04-28, 13:12 #6 Dr Sardonicus   Feb 2017 Nowhere 115538 Posts 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   2018-04-28, 15:01 #7 MARTHA   Jan 2018 43 Posts Thank you all !!! I got more answers than was expecting.. thanks a ton everyone    2018-04-28, 15:05   #8
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts Quote:
 Originally Posted by a1call 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   2018-04-29, 05:43 #9 CRGreathouse   Aug 2006 3×1,993 Posts Yet another answer, in PARI/GP: Code: chinese([Mod(5,6),Mod(7,10),Mod(2,15)])  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post MARTHA Number Theory Discussion Group 11 2018-03-02 15:55 Unregistered Information & Answers 10 2013-05-17 14:26 jasong Math 21 2012-02-13 16:05 ixfd64 PrimeNet 5 2008-05-21 13:39 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