Find smallest positive $a\in\mathbb Z$ such $10a\equiv 7\mod 17$.

Question

I found that the answer was $a=16$, I believe.

Note that $10a \equiv 7 \mod 17 \iff 17 \mid 10a - 7 \iff 10a -7 = 17x, x\in\mathbb Z$. The way I went about it was running EEA for $$10a + 17(-x) = 7,\quad x\in\mathbb Z.$$ I found it to be $1 = 10(-5)+17(3) \implies 7 = 10(-35)+17(21)$. But I wasn't sure where then I could find $16$ for this. I ended using bruteforce to find $a=16$ starting from 1. (not efficient).

Any more efficient alternative to find this such $a$ is appreciated!

You found that $10(-35)\equiv7 \bmod 17$. Note that $-35\equiv16 \bmod 17$. — Jaap Scherphuis, Nov 08 '21 at 13:54
Gotcha. I just need to apply the congruence relation again on the -35. Thanks! @JaapScherphuis — user10101, Nov 08 '21 at 13:58

score 3 · Accepted Answer · answered Nov 08 '21 at 13:59

3

If you're familiar with modular arithmetic: Note that $$5 \cdot 10 = 50 \equiv -1 \mod 17.$$ Thus, your equation is equivalent to $$-a \equiv 35 \mod 17.$$ Again reducing $35$, we get $$-a \equiv 1 \mod 17$$ or $$a \equiv -1 \mod 17.$$ It is now clear that the smallest positive such integer is $\boxed{16}$.

answered Nov 08 '21 at 13:59

Aryaman Maithani

15,771

1

Note for OP, it might seem that finding the inverse of $10$ (i.e. $-5\equiv 12$ here) seems to proceed out of guess and luck. Actually there is a procedure but it requires Fermat little theorem you probably are unaware of right now. In fact $10^{-1}\equiv 10^{15}\equiv 10\cdot 100^7\equiv 10\cdot 15^7\equiv 10\cdot(-2)^7\equiv -1280\equiv 12\pmod{17}$. – zwim Nov 09 '21 at 01:55

Find smallest positive $a\in\mathbb Z$ such $10a\equiv 7\mod 17$.

1 Answers1