How many integers $n$ are there which satisfy $1\leq n \leq 2014$ and $21n = 25 \pmod {29}$?
Asked
Active
Viewed 63 times
1
-
4Have you tried solving the linear congruence? – fretty Aug 18 '14 at 13:05
2 Answers
2
Hint: instead of using standard methods, this congruence is very easy to solve by simplifying the coefficients and cancelling: $$21n\equiv25\pmod{29}\quad\Leftrightarrow\quad -8n\equiv-4\pmod{29}\quad\Leftrightarrow\quad 2n\equiv1\pmod{29}$$ and so on.
David
- 82,662
-
+1 Nice one. The last one can be solved by using:
$$2n \equiv 1 \equiv 30 \pmod{29} \Leftrightarrow n \equiv 15 \pmod{29}$$
– Darth Geek Aug 18 '14 at 14:17 -
Since we are looking how many $n$ which satisfy $1\leq n \leq 2014$: So $2014/15=134$, thus there is 134 different $n$? – parco Aug 18 '14 at 14:46
0
Hint:
$$21^{-1} \equiv 18 \pmod{29}$$
Therefore:
$$18·21 n \equiv 18·25 \pmod{29} \Longrightarrow n \equiv 15 \pmod{29}$$
Darth Geek
- 12,296
-
-
Use Bezout's Identity to solve $21x + 29y = 1$. Then $x = 21^{-1} \pmod{29}$ – Darth Geek Aug 18 '14 at 14:15