
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
January 4th, 2017, 10:42 PM  #1 
Newbie Joined: Dec 2016 From: Dhaka, Bangladesh Posts: 9 Thanks: 0  remainder and a common divisor
By which number dividing 701, 1059, 1417 and 2312 we will get a common remainder? And what will be that remainder? Please tell me how this problem can be solved. 
January 4th, 2017, 11:37 PM  #2 
Senior Member Joined: Sep 2015 From: CA Posts: 1,105 Thanks: 576 
we can set it up as a system of equations $701 = n_1 k + r$ $1059 = n_2 k + r$ $1417 = n_3 k + r$ $2312 = n_4 k + r$ this has solution $\left (n_1, \dfrac{358}{k}+n_1,\dfrac{716}{k}+ n_1, \dfrac{1611}{k}+n_1\right)$ Now we know the $n$'s must all be integers so we find the greatest common factor of $358, 716, 1611$ Factoring these we find the greatest common factor is $k=179$ and $r = 164$ 
January 5th, 2017, 06:47 AM  #3 
Newbie Joined: Dec 2016 From: Dhaka, Bangladesh Posts: 9 Thanks: 0 
I am afraid to say that I don't understand how we can write n1, (358/k)+n1, (716/k)+n1, (1611/k)+n1 from 701=n1k+r 1059=n2k+r 1417=n3k+r 2312=n4k+r. Please explain a little bit. 
January 5th, 2017, 07:57 AM  #4 
Member Joined: Dec 2016 From: USA Posts: 46 Thanks: 11 
Using romsek's notation, suppose \begin{align} 701 &= n_1 k + r\\ 1059 &= n_2 k + r\\ 1417 &= n_3 k + r\\ 2312 &= n_4 k + r \end{align} for some integer $k > 1$, and some integer $r$, $0 \le r < k$. Take any pair of the above equations and subtract one from the other. Note that after the subtraction, the new RHS is a multiple of k. It follows that $k$ must be a factor of the new LHS. Thus, $k$ is a common factor of each of the differences $1059  701$, $14171059$, $23121417$Any common factor greater than $1$ would qualify as a possible value of $k$, but since the statement of problem implies that the answer is unique, there better be only one such factor (else there would be more than one possible answer). Using that knowledge, you can expect that $k$ is prime. Since $23121417$ is odd, $k$ must be odd. Since $1059  701= 358 = 2\cdot 179$, and since $179$ is prime, $k$ must be 179. Of course it's worth checking (just to be sure) that $179$ divides all three differences. To find $r$, find the remainder when any of the original numbers is divided by $179$ (might as well use the smallest $701$). 
January 5th, 2017, 11:00 AM  #5 
Math Team Joined: Oct 2011 From: Ottawa Ontario, Canada Posts: 8,752 Thanks: 604 
"By which number dividing 701, 1059, 1417 and 2312 we will get a common remainder?" That's unclear to me; does it mean: 701, 1059, 1417 and 2313 are all divided by positive integer n. In each of the 4 cases, the remainder equals positive integer r. Find n. And this could be given as an example: 17, 44, 65, 89 17 / 3 = 5 r=2 44 / 3 = 14 r=2 65 / 3 = 21 r=2 89 / 3 = 29 r=2 So a solution: n = 3. Do I need another coffee? 
January 5th, 2017, 12:29 PM  #6  
Senior Member Joined: Sep 2015 From: CA Posts: 1,105 Thanks: 576  Quote:
 
January 5th, 2017, 12:57 PM  #7  
Member Joined: Dec 2016 From: USA Posts: 46 Thanks: 11  Quote:
Quote:
Quote:
As I described in my previous reply, $n$ can be any common factor of the differences between successive pairs (e.g., the gaps). Thus for the 4 term sequence $17, 44, 65, 89$ that you give above, there are 3 gaps, namely $27, 21, 24$. The gcd of those 3 numbers is $3$. Any positive integer which divides the gcd would also give a valid $n$. If we explicitly exclude $n = 1$ (which would always work), then in this case, the only valid $n$ is $n = 3$. You seem OK for now.  
January 5th, 2017, 04:10 PM  #8 
Newbie Joined: Dec 2016 From: Dhaka, Bangladesh Posts: 9 Thanks: 0 
Thanks to everyone. Now I have got this fact.


Tags 
common, divisor, remainder 
Search tags for this page 
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Greatest Common Divisor  classkid  Algebra  3  September 21st, 2016 05:59 AM 
The greatest common divisor  mared  Algebra  5  February 14th, 2014 11:15 AM 
greatest common divisor  michael1270  Number Theory  0  September 11th, 2013 09:58 AM 
Least and Greatest Common divisor  srw899  Algebra  4  March 13th, 2009 04:05 AM 
Greatest Common Divisor  johnny  Algebra  0  November 17th, 2007 04:58 PM 