Processing math: 100%
 
+0  
 
+5
5203
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+26397 
+19

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

 

(1)1754r(modn)(2)1457r(modn)(1)1754r=anaZ(2)1457r=bnbZba(1)r=1754an(2)r=1457bn(1)=(2)1754an=1457bn297=n(ab)|n is max, when (ab)=1n=297(1)1754269(mod297)(2)1457269(mod297)

 

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

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

 

(1)1754r(modn)(2)1457r(modn)(1)1754r=anaZ(2)1457r=bnbZba(1)r=1754an(2)r=1457bn(1)=(2)1754an=1457bn297=n(ab)|n is max, when (ab)=1n=297(1)1754269(mod297)(2)1457269(mod297)

 

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

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

 

(1)1457r(modn)(2)368r(modn)(1)1457r=bnbZ(2)368r=cncZcb(1)r=1457bn(2)r=368cn(1)=(2)1457bn=368cn1089=n(bc)|n is max, when (bc)=1n=1089(1)1457368(mod1089)(2)368368(mod1089)

 

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

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

 

(1)1754r(modn)(2)368r(modn)(1)1754r=anaZ(2)368r=cncZca(1)r=1754an(2)r=368cn(1)=(2)1754an=368cn1386=n(ac)|n is max, when (ac)=1n=1386(1)1754368(mod1386)(2)368368(mod1386)

 

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

 d. What is the largest positive integer n such that 1754, 1457 and 368  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.

 The prime factorisation all differences: (1)297=3311(2)1386=232711(3)1089=32112

 

III.

 The greatest n is the greatest common divider of the differences: (1)297=33211(2)1386=273211(3)1089=113211  n=gcd(297,1386,1089)=99  

 

IV.

 The greatest n is 3211=99. The same remainder is 71 : (1)175471(mod99)(2)145771(mod99)(3)36871(mod99)

 

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

175471mod99145771mod9936871mod99

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

Thank you Bertie,

i have corrected the prime number factorisation!

 

 Jul 15, 2015

0 Online Users