+0

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

+5
1098
6
+1766

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
+18827
+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
Sort:

#1
+18827
+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
+18827
+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
+18827
+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
+18827
+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
+18827
+10

Thank you Bertie,

i have corrected the prime number factorisation!

heureka  Jul 15, 2015

### 24 Online Users

We use cookies to personalise content and ads, to provide social media features and to analyse our traffic. We also share information about your use of our site with our social media, advertising and analytics partners.  See details