+0  
 
0
456
8
avatar

N is a four-digit positive integer. Dividing N by 9, the remainder is 5. Dividing N by 7, the remainder is 4. Dividing N by 5, the remainder is 1. What is the smallest possible value of N?

 Apr 20, 2021
 #1
avatar+109 
0

The smallest 4-digit n =1256

 

1256 mod 9 =5

1256 mod 7 =3

1256 mod 5 =1

 Apr 20, 2021
 #3
avatar+118587 
+1

How did you arrive at this answer Hannah?

 

I do not understand your working either guest.  What is CRT + MMI  ?

Melody  Apr 20, 2021
 #4
avatar+2401 
+1

I'm not quite sure how Hannah or Guest got their answers, but I think there's a theorem called Chinese remainder theorem that you can use. 

 

x = 5 (mod 9)

x = 3 (mod 7)

x = 1 (mod 5)

 

To use the chinese remainder therum, the gcd of all mods much be 1. 

gcd(9, 7) = 1

gcd(7, 5) = 1

gcd(9, 5) = 1

 

It's a bit hard to explain, but there are good videos on it on yt. :))

One by "Randell Heyman."

 

Are mods are 9, 7, and 5.

      (not 9)   (not 7)  (not 5)

x = (7*5) + (9*5) + (9*7)

 

First part (9 mod)

Now, it gets a bit confusing. 

(9*5) and (9*7) will both be 0 in mod 9 (multiple of 9)

So we need to find a y*7*5 = 5 in mod 9. 

y = 4. 

 

Second part (7 mod)

x = (4*7*5) + (9*5) + (9*7)

(4*7*5) and (9*7) will both be 0 in mod 7.

(y*9*5) = 3 in mod 7. 

y = 1, 45 = 3 in mod 7

 

Third part (5 mod)

x = (4*7*5) + (9*5) + (9*7)

(4*7*5) and (9*5) will both be 0 in mod 5. 

(9*7*y) = 1 in mod 5

y = 2

 

Final equation

x = (4*7*5) + (9*5) + (9*7*2) = 311

 

Yayyy, it works. :))

I learned smth new today. 

However, we need a 4 digit number. 

311+(9*7*5)y = smallest 4 digit number

x = 1256

 

That has to be the most terrible explanation ever... but I tried. :)

 

 

=^._.^=

catmg  Apr 20, 2021
 #5
avatar
+1

Read the question carefully!

 

N mod 9 ==5

N mod 7 ==4  [NOT 3]

N mod 5 ==1

 

See this link here:  https://web2.0calc.com/questions/congruences

Guest Apr 20, 2021
edited by Guest  Apr 20, 2021
 #6
avatar+2401 
+1

Oops. 

Nice job for catching the mistakes. :))

 

=^._.^=

catmg  Apr 20, 2021
 #7
avatar+118587 
+2

It doesn't matter that you copied the question incorrectly catmg.  It is not YOUR homework.

You explained your method the best you could and that is all that counts. 

The asker is always expected to check then accept, edit or reject the answers given to them.

 

I learned from your answer in that I looked up the Chinese remainder theorem.  Thanks  laughcoollaugh

This is the video that I learned from.  I found it excellent.

It is from a channel called "Maths with Jay"

I got the answer 1166    (which is the same as our first guest's answer.)     laugh

 

 

https://www.youtube.com/watch?v=zIFehsBHB8o

Melody  Apr 21, 2021
edited by Melody  Apr 21, 2021
 #8
avatar+2401 
+1

Aww thank you. :))

I should be more careful in the future, I keep messing up with these mistakes in contests. 

 

I just watched the video, modular stuff is always very tricky.

 

=^._.^= 

catmg  Apr 21, 2021
 #2
avatar
+1

Using CRT + MMI

 

315 m +  221, where m=0, 1, 2, 3...........

 

The smallest 4-digit poitive integer is:

 

[315 * 3  +  221]==1,166

 Apr 20, 2021

1 Online Users

avatar