+0  
 
+5
5194
6
avatar+1836 

a.  What is the largest positive integer $n$ such that 1457 and 1754 leave the same remainder when divided by $n$?

b.  What is the largest positive integer $n$ such that $1457$ and $368$ leave the same remainder when divided by $n$?

c.  What is the largest positive integer $n$ such that $1754$ and $368$ leave the same remainder when divided by $n$?

d.  What is the largest positive integer $n$ such that $1457$, $1754$, and $368$ all leave the same remainder when divided by $n$?

 Jul 13, 2015

Best Answer 

 #1
avatar+26393 
+19

$$\\\small{\text{
a. What is the largest positive integer $n$ such that 1457 and 1754 }}\\
\small{\text{
leave the same remainder $r$ when divided by $n$?
}}$$

 

$$\small{\text{$
\begin{array}{lrcl}
(1) & 1754 &\equiv & r \pmod n\\
(2) & 1457 &\equiv & r \pmod n\\
\\
\hline
\\
(1) & 1754-r &=& a\cdot n \qquad a\in Z \\
(2) & 1457-r &=& b\cdot n \qquad b\in Z \qquad b\ne a\\
\\
\hline
\\
(1) & r &=& 1754- a\cdot n \\
(2) & r &=& 1457- b\cdot n \\
\\
\hline
\\
(1)=(2) & 1754- a\cdot n &=& 1457- b\cdot n\\
& 297 &=& n\cdot (a-b) \qquad | \qquad n \mathrm{~is~ max, ~when ~}(a-b) = 1\\
& \mathbf{n} & \mathbf{=} & \mathbf{297}
\\
\hline
\\
(1) & 1754 &\equiv & 269 \pmod{297} \\
(2) & 1457 &\equiv & 269 \pmod{297}
\end{array}
$}}$$

 

.
 Jul 14, 2015
 #1
avatar+26393 
+19
Best Answer

$$\\\small{\text{
a. What is the largest positive integer $n$ such that 1457 and 1754 }}\\
\small{\text{
leave the same remainder $r$ when divided by $n$?
}}$$

 

$$\small{\text{$
\begin{array}{lrcl}
(1) & 1754 &\equiv & r \pmod n\\
(2) & 1457 &\equiv & r \pmod n\\
\\
\hline
\\
(1) & 1754-r &=& a\cdot n \qquad a\in Z \\
(2) & 1457-r &=& b\cdot n \qquad b\in Z \qquad b\ne a\\
\\
\hline
\\
(1) & r &=& 1754- a\cdot n \\
(2) & r &=& 1457- b\cdot n \\
\\
\hline
\\
(1)=(2) & 1754- a\cdot n &=& 1457- b\cdot n\\
& 297 &=& n\cdot (a-b) \qquad | \qquad n \mathrm{~is~ max, ~when ~}(a-b) = 1\\
& \mathbf{n} & \mathbf{=} & \mathbf{297}
\\
\hline
\\
(1) & 1754 &\equiv & 269 \pmod{297} \\
(2) & 1457 &\equiv & 269 \pmod{297}
\end{array}
$}}$$

 

heureka Jul 14, 2015
 #2
avatar+26393 
+13

$$\\\small{\text{
b. What is the largest positive integer $n$ such that 1457 and 368 }}\\
\small{\text{
leave the same remainder $r$ when divided by $n$?
}}$$

 

$$\small{\text{$
\begin{array}{lrcl}
(1) & 1457 &\equiv & r \pmod n\\
(2) & 368 &\equiv & r \pmod n\\
\\
\hline
\\
(1) & 1457-r &=& b\cdot n \qquad b\in Z \\
(2) & 368-r &=& c\cdot n \qquad c\in Z \qquad c\ne b\\
\\
\hline
\\
(1) & r &=& 1457- b\cdot n \\
(2) & r &=& 368- c\cdot n \\
\\
\hline
\\
(1)=(2) & 1457- b\cdot n &=& 368- c\cdot n\\
& 1089 &=& n\cdot (b-c) \qquad | \qquad n \mathrm{~is~ max, ~when ~}(b-c) = 1\\
& \mathbf{n} & \mathbf{=} & \mathbf{1089}
\\
\hline
\\
(1) & 1457 & \equiv & 368 \pmod{1089} \\
(2) & 368 & \equiv & 368 \pmod{1089} \\
\end{array}
$}}$$

 

.
 Jul 14, 2015
 #3
avatar+26393 
+8

$$\\\small{\text{
c. What is the largest positive integer $n$ such that 1754 and 368 }}\\
\small{\text{
leave the same remainder $r$ when divided by $n$?
}}$$

 

$$\small{\text{$
\begin{array}{lrcl}
(1) & 1754 &\equiv & r \pmod n\\
(2) & 368 &\equiv & r \pmod n\\
\\
\hline
\\
(1) & 1754-r &=& a\cdot n \qquad a\in Z \\
(2) & 368-r &=& c\cdot n \qquad c\in Z \qquad c\ne a\\
\\
\hline
\\
(1) & r &=& 1754- a\cdot n \\
(2) & r &=& 368- c\cdot n \\
\\
\hline
\\
(1)=(2) & 1754- a\cdot n &=& 368- c\cdot n\\
& 1386 &=& n\cdot (a-c) \qquad | \qquad n \mathrm{~is~ max, ~when ~}(a-c) = 1\\
& \mathbf{n} & \mathbf{=} & \mathbf{1386}
\\
\hline
\\
(1) & 1754 &\equiv& 368 \pmod{1386} \\
(2) & 368 &\equiv& 368 \pmod{1386} \\
\end{array}
$}}$$

 

.
 Jul 14, 2015
 #4
avatar+26393 
+13

$$\\\small{\text{
d. What is the largest positive integer $n$ such that 1754, 1457 and 368 }}\\
\small{\text{
all leave the same remainder $r$ when divided by $n$?
}}$$

 

I.

$$\small{\text{
In a. we habe the difference $1754-1457 = 297 $
}} \\
\small{\text{
In b. we habe the difference $1754-368= 1386 $
}} \\
\small{\text{
In c. we habe the difference $1457 -368= 1089 $
}} \\
\begin{array}{lrcl}
\end{array}
}}$$

 

II.

$$\small{\text{
The prime factorisation all differences:
}} \\ \\
\small{\text{$
\begin{array}{lrcl}
(1) & 297 &=& 3^3\cdot 11 \\
(2) & 1386 &=& 2\cdot 3^2\cdot 7 \cdot 11 \\
(3) & 1089 &=& 3^2 \cdot 11^2 \\
\end{array}
$}} \\$$

 

III.

$$\small{\text{
The greatest $n$ is the greatest common divider of the differences:
}} \\ \\
\small{\text{$
\begin{array}{lrcll}
(1) & 297 &=& 3 &\mathbf{ \cdot 3^2 \cdot 11 }\\
(2) & 1386 &=& 2\cdot 7 &\mathbf{ \cdot 3^2 \cdot 11 }\\
(3) & 1089 &=& 11 &\mathbf{ \cdot 3^2 \cdot 11 }\\
\end{array}
$}} \\
\small{\text{$
\boxed{~~
n= gcd {(297,1386,1089)}=99 ~~}
$}}$$

 

IV.

$$\small{\text{
The greatest $n$ is $3^2\cdot 11 = 99$. The same remainder is 71 :
}} \\ \\
\small{\text{$
\begin{array}{lrcll}
(1) & 1754 &\equiv & 71 \pmod{99} \\
(2) & 1457 &\equiv & 71 \pmod{99} \\
(3) & 368 &\equiv & 71 \pmod{99}
\end{array}
$}} \\$$

 

.
 Jul 15, 2015
 #5
avatar+893 
+12

$$\displaystyle \\1754 \equiv 71 \mod99\\1457\equiv 71 \mod 99 \\ 368 \equiv 71 \mod 99$$

.
 Jul 15, 2015
 #6
avatar+26393 
+12

Thank you Bertie,

i have corrected the prime number factorisation!

 

 Jul 15, 2015

1 Online Users

avatar