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

$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.

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

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

$143 = 2\times 67 + 9$

$67 = 7 \times 9 +4$

$9 = 2\times 4 +1$

Hence $1 = 9 - 4\times 2$

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

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

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

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

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

This tells us that $67\times (-30) \equiv 1 \pmod{143}$ hence $67\times (143-30) \equiv 1 \pmod{143}$

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

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

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

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

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