+0

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

+5
1651
6
+1793

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

Mellie  Jul 13, 2015

#1
+19990
+15

$$\\\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
#1
+19990
+15

$$\\\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
+19990
+10

$$\\\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} }}$$

heureka  Jul 14, 2015
#3
+19990
+5

$$\\\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} }}$$

heureka  Jul 14, 2015
#4
+19990
+10

$$\\\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} }} \\$$

heureka  Jul 15, 2015
#5
+889
+10

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

Bertie  Jul 15, 2015
#6
+19990
+10

Thank you Bertie,

i have corrected the prime number factorisation!

heureka  Jul 15, 2015