Question 53236: Find least no in which when divide by 5,7,9 then it leaves remainder 1,2,3 respectively. What is logic for solving this problem.
Answer by venugopalramana(3286)   (Show Source):
You can put this solution on YOUR website! Find least no in which when divide by 5,7,9 then it leaves remainder 1,2,3 respectively. What is logic for solving this problem.
I AM NOT SURE HOW FAR YOU STUDIED ON THEORY OF NUMBERS..SO LET ME GIVE YOU A
COMMONSENSE APPOACH.......AND DOWN BELOW BASED ON THEORY OF NUMBERS
LET THE NUMBER BE .....N
N-1|5............N= 5M+1...WHERE M IS AN INTEGER.............1
N-2|7............5M+1-2|7.....5M-1|7...........5M-1=7P......2
N-3|9............5M-2|9......5M-2=9Q........................3
NOW USE EQN.3 BY GIVING Q INCREASING VALUES AND TESTING EQN 2.NOTE THAT P,Q,M,N SHOULD ALL BE INTEGERS.
I.TRY..Q=2.........5M-2=9*2=18.....M=4....BUT THIS CANT SATISFY EQN2
NEXT JUMP WILL BE TO Q=2+5=7
II.TRY.Q=7.........................M=13....NO(NOTE THAT M INCREASES IN STEPS OF 9...FOR Q INCREASIN IN STEPS OF 5)
III..Q=12..........................M=22.......NO
IV...Q=17..........................M=31......YES..5*31-1=154|7=22
SO........... N=5*31+1=156..
-------------------------------------------------------------------------
BASED ON CONGRUENCE MODULO
(5,7)=(5,9)=(7,9)=1 HENCE THERE IS A SOLUTION.
N = 1(MOD 5)=2(MOD 7) = 3(MOD 9)
N= 1+5M.....
1+5M=2(MOD 7)
5M = 1(MOD 7)....ADD 0 =14(MOD 7) TO BOTH SIDES
5M = 15 (MOD 7)
M = 3 (MOD 7)
M = 7P+3
N = 1+5(7P+3)=1+35P+15=35P+16
35P+16 = 3 (MOD 9)
35P = -13 (MOD 9).......ADD 0=153(MOD 9)
35P=140(MOD 9)
P=4(MOD 9)=9Q+4
N= 35P+16 = 35(9Q+4)+16=315Q+156
HENCE WE GET DIFFERENT SOLUTIONS FOR THE CONGRUENCIES BY PUTTING Q=0,1,2...ETC
N= 156,571,786...ETC...
LEAST VALUEOF N IS 156 AS GOT BOVE.
|
|
|
