I'm trying to solve a simple congruence like $23d\equiv 1 (mod40)$ and so I'm using the method I found on Wikipedia (http://en.wikipedia.org/wiki/Linear_congruence_theorem). So finally I arrive at the conclusion that $d=40k+7$ for some integer $k$ and here's where I get stuck - how can I found all the solutions (here I know there's only one since $GCD(23, 40) = 1$ but I'm also talking about different problems) if not by taking some random values and plugging in everything I think of incrementally?
I mean: I know the solution is $k=0$ and so $d=7$ only thanks to the wild guess of "let's try 0 first" and scoring a jackpot then but how do I derive it rather than by common sense?
Answer
You're just a step away: $$23 d \equiv 1 \pmod {40} \implies d = 40k + 7 \iff d - 7 = 40 k $$ $$\iff d\equiv 7 \pmod {40}$$
So every solution $d$ satisfying your congruence equation is expressible, as you've shown, by $$d = 40k + 7 \iff 40\mid (d - 7)$$. There are infinitely many values of $k$ for which this is true.
Any unique integer $k \in \mathbb{Z}$ yields a value satisfying $d = 40k + 7\;$ such that $d \equiv 7 \pmod {40}$. In other words, the values of $d$ which satisfy your congruence equation are all $d$ for which $40 \mid (d - 7)$. There are infinitely many $d$ congruent to $7 \mod 40$.
It is standard, however, by convention, that we choose $k$ so that we have $0 \leq d \lt m$ where m is the modulus. So in this case, we choose $d = 0 \cdot 40 + 7$ to represent the equivalence class of all solutions: and represent the solution as $d \equiv 7 \mod 40,$ because $d = 7$ is the only solution $0 \leq 7 \lt 40$.
No comments:
Post a Comment