My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
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.
Nousher Ahmed is offline  
 
January 4th, 2017, 11:37 PM   #2
Senior Member
 
romsek's Avatar
 
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$
romsek is offline  
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.
Nousher Ahmed is offline  
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$).
quasi is offline  
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?
Denis is offline  
January 5th, 2017, 12:29 PM   #6
Senior Member
 
romsek's Avatar
 
Joined: Sep 2015
From: CA

Posts: 1,105
Thanks: 576

Quote:
Originally Posted by Denis View Post
"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.
romsek is offline  
January 5th, 2017, 12:57 PM   #7
Member
 
Joined: Dec 2016
From: USA

Posts: 46
Thanks: 11

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

Quote:
Originally Posted by Denis View Post
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 View Post
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 View Post
Do I need another coffee?
You seem OK for now.
quasi is offline  
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.
Nousher Ahmed is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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





Copyright © 2017 My Math Forum. All rights reserved.