1
$\begingroup$

Find a solution $x $ to the following congruence:

$$2x \equiv 7 \pmod{11} $$.

So my issue is not in solving this exact problem, I am more curious if there is a more efficient way of solving these sorts of questions besides trying every integer that would be in the set $S = \{0,....m-1\}$ ? This is my first number theory class, so if there is an extremely advanced way then i don't think i would be ready to understand it.

Also to do with this question and in the general sense how do we treat the values of $x $ that produce integers that are smaller than our modulus? For example in this question when $x = 0,1,2..5$ each of those produce a number less than our modulus 11. Now i know it is possible they could have a negative congruence but do we treat these sorts of values in any other way?

$\endgroup$
  • 1
    $\begingroup$ $2x\equiv 7\pmod {11}\implies 2x-11y=7$, which is an $Diophantine\; equation$. Now, can you solve? If you don't know about Diophantine equation, then simply count yourself, and put down the solutions using your intuition. $\endgroup$ – user249332 Sep 20 '15 at 17:43
  • $\begingroup$ I learned diophantine awhile back, but i am going to have to go refresh myslf how to do them, but i am familiar with the idea. How about treating the lesser values in comparison to my modulus? $\endgroup$ – dc3rd Sep 20 '15 at 17:47
  • $\begingroup$ Are you familiar with introductory ring theory and know that $(\mathbb{Z}_p,+_p,\times_p)$ is a field when $p$ is a prime (implying that every element in $\mathbb{Z}_p\setminus\{0\}$ has a multiplicative inverse)? You can then write $x$ as $2^{-1}\cdot 7$ since then $2x=2\cdot 2^{-1}\cdot 7=7$ $\endgroup$ – JMoravitz Sep 20 '15 at 17:49
  • $\begingroup$ What did you mean by 'lesser values'. $\endgroup$ – user249332 Sep 20 '15 at 17:49
  • $\begingroup$ @JMoravitz, not at ring theory yet, but now I get the jist of at what level the "more efficient idea" exists at. $\endgroup$ – dc3rd Sep 20 '15 at 17:57
3
$\begingroup$

First answering your second question. When considering congruences we do not consider $x$ as a natural number or integer, but rather a set (class) of numbers, e.g. in $x \equiv 2 \mod 11 \iff x \in \{...,-9,2,13,24,...\}$. I think it helps to view this from another viewpoint that makes the 'modular arithmetic' somewhat clearer: In group theory we consider the group $G = \mathbb Z / 11 \mathbb Z$ whose elements are of the form $n+11\mathbb Z$, basically this whole set. But $2+11\mathbb Z$ is the same element as $13 + 11 \mathbb Z$, these two are just other representations of the same element.

For answering the second question it would be beneficial to know about your knowledge: Do you know about the chinese remainder theorem? Do you know about the Euclidean algorithm? Or do you know about group theory?

I think @Subhadeep Dey's comment will help you a lot, and I recommend reading about the GCD as well as the Euclidean algorithm for this problem.

$\endgroup$
  • $\begingroup$ Excellent solution.+1 $\endgroup$ – user249332 Sep 20 '15 at 17:50
  • $\begingroup$ +1: Though, I would say $x\in\{\dots,-9,2,13,24,\dots\},$ instead. $\endgroup$ – Cameron Buie Sep 20 '15 at 17:52
  • $\begingroup$ @CameronBuie Thats what I wanted to write, I'll change it, thanks! $\endgroup$ – flawr Sep 20 '15 at 17:53
  • $\begingroup$ I should've read this before i commented to Subhadeep. But you guys answered it in terms of what i should know at this stage. Currently i have just started re-doing number theory. Though aware of the conceptsyou have mentioned, I still have to work on these fundamentals in modular arithematic before i take on those ideas. Thanks for the help $\endgroup$ – dc3rd Sep 20 '15 at 18:01
  • $\begingroup$ Actually looking at it again that idea of looking at $x $ as a set is very enlightening. $\endgroup$ – dc3rd Sep 20 '15 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.