All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
A system of modular equations (Posted on 2008-07-20) Difficulty: 3 of 5
Solve the following set of equations for positive integers a and b:

1919(a)(b) mod 5107 = 1
1919(a+1)(b-1) mod 5108 = 5047
1919(a+2)(b-2) mod 5109 = 1148
1919(a+3)(b-3) mod 5110 = 3631
1919(a+4)(b-4) mod 5111 = 2280

See The Solution Submitted by pcbouhid    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Solution | Comment 1 of 8

Reducing the given equations by their respective modulii, the first four equations can be  rewritten as:

1919 (a)(b) (mod 5107) = 1
1919 (ab-a+b) (mod 5108) = 1858
1919 (ab-2a+2b) (mod 5109) = 3715
1919 (ab-3a+3b) (mod 5110) = 2318


In the fifth given equation, we observe that: gcd (1919, 5111, 2280) = 19, so that upon division by 19, the equation now becomes:

101 (a+4)(b-4) (mod 269) = 120
or, 101(ab-4a+4b) (mod 269) = 122

We now denote the respective modular inverses of 1919 in mod 5107, mod 5108, mod 5109, mod 5110 in turn by A(1), A(2), A(3), A(4) and the modular inverse of 101 mod 269 by A(5).

By way of a little trial and error, we obtain:

A(1) = 165; A(2) = 2007; A(3) = 2657; A(4) = 3949, and A(5) = 8.

Accordingly, we must have:

(ab) (mod 5107) = 165

(ab-a+b) (mod 5108) = (1858*2007) (mod 5108) = 166

(ab-2a+2b) (mod 5109) = (3715*2657) (mod 5109) = 167

(ab-3a+3b) (mod 5110) = (462*3949) (mod 5110) = 168

(ab-4a+4b) (mod 269) = (122*8) (mod 269) = 169............(I)

Adding 5107(a-b), 5108(a-b), 5109(a-b), 5110(a-b), 5111(a-b) in turn to the lhs of the system of equations  in (I), subtracting 5107, 5108, 5109, 5110, 5111 in turn from each of the rhs in (I), and upon subsequent rearrangement, we obtain:

(ab+5107(a-b) + 4942) (mod 5107) = 0

(ab+5107(a-b) + 4942) (mod 5108) = 0

(ab+5107(a-b) + 4942) (mod 5109) = 0

(ab+5107(a-b) + 4942) (mod 5110) = 0

(ab+5107(a-b) + 4942) (mod 269) = 0  ................(II)


Accordingly, we must have:

((ab+5107(a-b) + 4942) (mod L) = 0,
where: L = LCM(5107, 5108, 5109, 5110, 269)
= 91,600,075,916,256,180

or, (a-5107)(b+5107) (Mod L) = -26086391, and http://www.virtuescience.com/prime-factor-calculator.html
gives the prime factorization of  26086391 as 4241*6151 apart from the trivial factorization 1*N,  where N = 26086391.


Thus, (a-5107, b+5107) (mod L) = (-4241, 6151), (4241, -6151), (6151, -4241), (-6151, 4241), (1, -N),
(-1, N), (N, -1), (-N, 1)

The only positive pair (a,b) occurs whenever (a-5107, b+5107) (mod L) = (-4241, 6151), (-1, N): giving:

(a, b) (Mod L) = (866, 1044), (5106, 26081284)

Now, each of 866, 1044, 5106 and 26081284  is less than L.

Consequently,  (a, b) = (866, 1044), (5106, 26081284) are the only possible solutions to the given problem.

Note:  There were some typing errors in this post, and these anomalies have been subsequently edited in the light of the comments in the subsequent posts.

Edited on August 1, 2008, 6:41 am
  Posted by K Sengupta on 2008-07-20 14:26:13

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (0)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information