My Math Forum remainder and a common divisor

 Number Theory Number Theory Math Forum

 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: Southern California, USA Posts: 1,603 Thanks: 816 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$, $1417-1059$, $2312-1417$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 $2312-1417$ 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: 10,906 Thanks: 716 "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: Southern California, USA

Posts: 1,603
Thanks: 816

Quote:
 Originally Posted by Denis "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?
good catch. I just assumed they wanted the largest such divisor.

January 5th, 2017, 12:57 PM   #7
Member

Joined: Dec 2016
From: USA

Posts: 46
Thanks: 11

Quote:
 Originally Posted by Denis By which number dividing 701, 1059, 1417 and 2312 we will get a common remainder?
By $179$.

Quote:
 Originally Posted by Denis 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.
Yes, although in my reply I called it $k$, not $n$.

Quote:
 Originally Posted by Denis 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.
Yes, but the question is, how do you find $n$?

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$.

Quote:
 Originally Posted by Denis Do I need another coffee?
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

### By which number dividing 701, 1059, 1417 and 2312 we will get a common remainder?

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post classkid Algebra 3 September 21st, 2016 06:59 AM mared Algebra 5 February 14th, 2014 11:15 AM michael1270 Number Theory 0 September 11th, 2013 10:58 AM srw899 Algebra 4 March 13th, 2009 05:05 AM johnny Algebra 0 November 17th, 2007 04:58 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top