What is the smallest positive integer ending in 1986 which is divisible by 1987?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
I would like to know how to write "congruent to" in Latex.
Log in to reply
Generally press "more" (down-right corner of every problem) and choose "Toggle LaTex"
can someone tell me what the technique used to determine 214 65-7 1987=1 is called, like the steps after the Euclidean Algorithm, like why are those steps taken, what is the thought process, and why go through the EA to determine the greatest common factor
Here's a simple python script that gives you the answer:
1 2 3 4 5 6 |
|
using M a t h e m a t i c a
Select[Range@1000,Mod[FromDigits@Join[IntegerDigits@#,{1,9,8,6}],1987]==0&]
returns 214
Problem Loading...
Note Loading...
Set Loading...
Let the number be a
Now, a 1 9 8 6 ≡ 0 ( m o d 1 9 8 7 ) [where a 1 9 8 6 = a ∗ 1 9 8 6 ]
We can write a1986 as a ∗ 1 0 4 + 1 9 8 6
a ∗ 1 0 4 + 1 9 8 6 ≡ 0 ( m o d 1 9 8 7 )
a ∗ 1 0 4 − 1 ≡ 0 ( m o d 1 9 8 7 )
a ∗ 1 0 4 ≡ 1 ( m o d 1 9 8 7 )
Now, 1 0 4 ≡ 6 5 ( m o d 1 9 8 7 )
6 5 ∗ a ≡ 1 ( m o d 1 9 8 7 )
Now, use Euclid's algorithm,
1 9 8 7 = 6 5 ∗ 3 0 + 3 7
6 5 = 3 7 + 2 8
3 7 = 2 8 + 9
2 8 = 9 ∗ 3 + 1
Hence,
1 = 2 8 − 9 ∗ 3
= 2 8 − 3 ( 3 7 − 2 8 )
= 4 ( 6 5 − 3 7 ) − 3 ( 3 7 )
= 4 ( 6 5 ) − 7 ( 1 9 8 7 − 6 5 ∗ 3 0 )
1 = 2 1 4 ( 6 5 ) − 7 ( 1 9 8 7 )
Hence, 214(65) = 1 mod 1987
As a result a = 214, therefore smallest positive integer is 2 1 4 1 9 8 6