143 is special ...

For how many positive integers k < 10000 k<10000 does the following statement hold ?

67 × k 1 ( m o d 143 ) 67\times k \equiv 1 \pmod{143}


The answer is 70.

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.

2 solutions

Aditya Raut
May 22, 2014

By using Bezout's theorem we can say that there exists exactly 1 positive integer k < 143 k<143 which has the stated property . It's possible to find the number by using Bezout's theorem , as g c d ( 67 , 143 ) = 1 gcd(67,143)=1

Thus 1 can be expressed as 143 x + 67 y 143x +67y for some integers x x and y y .

143 = 2 × 67 + 9 143 = 2\times 67 + 9

67 = 7 × 9 + 4 67 = 7 \times 9 +4

9 = 2 × 4 + 1 9 = 2\times 4 +1

Hence 1 = 9 4 × 2 1 = 9 - 4\times 2

1 = ( 143 2 × 67 ) ( 67 7 × 9 ) 2 \therefore 1 = (143 - 2\times 67) - (67- 7\times 9) 2

1 = ( 143 2 × 67 ) [ 2 × 67 14 ( 143 2 × 67 ) ] \therefore 1 = (143 - 2\times 67) - [2\times 67- 14(143 - 2\times 67) ]

1 = 143 2 × 67 + 14 × 143 30 × 67 \therefore 1 = 143 - 2\times 67 +14\times 143 -30 \times 67

1 = 143 × 15 67 × 30 \therefore 1 = 143 \times 15 - 67\times 30

1 = 143 × 15 + 67 × ( 30 ) \therefore 1 = 143 \times 15 + 67\times (-30)

This tells us that 67 × ( 30 ) 1 ( m o d 143 ) 67\times (-30) \equiv 1 \pmod{143} hence 67 × ( 143 30 ) 1 ( m o d 143 ) 67\times (143-30) \equiv 1 \pmod{143}

So the smallest positive integer for which given statement hold is 143-30 i.e. 111 111

The other numbers will be of the form 111 + 143 k 111 +143k as they also will be congruent to 1 mod 143 .

The multiple of 143 next to 10000 is 143 × 70 = 10010 143 \times 70 = 10010 so the biggest of our required numbers is 10010 111 = 111 + 69 × 143 10010-111= 111 + 69 \times 143 .

Hence all the numbers we require are 111 , 111 + 143 , 111 + 2 × 143 , , 111 + 69 × 143 111,111+143 , 111+2\times 143 ,\dots, 111+ 69\times 143

Thus there are 70 \boxed{70} such numbers k k ............. ( k < 10000 ) (k<10000)

I salute you dear

Himanshu Patil - 7 years ago

Log in to reply

Thanks , I feel blessed for your replies @Abhimanyu Swami and @Himanshu Patil :D

Aditya Raut - 7 years ago

Log in to reply

i guess lol

math man - 6 years, 7 months ago

Wow....completely baffled by your solution.......... there's much more for me to learn in modular arithmetic.

Led Tasso - 7 years ago

I have another approach...

Since k is the inverse of 67, it is unique in the interval [1, 143]. Since 143 = 11 x 13, 67k is congruent to 1 modulo11 and modulo 13. By property of LCD congruence, this holds true. Using Chinese Remainder Theorem, we found out that k = 111 + 143n so k is congruent to 111 modulo 143. From this, we solve the inequality 111 + 143(n-1) < 10000. And n <= 70 < 70 + (22/143). Hence, the answer is 70.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...