2

New to congruences & Number Theory

Below is text from the book Joseph H. Silverman: A Friendly Introduction to Number Theory, 4th Edition, chapter 8, page 56.

To solve

$4x\equiv 3 \pmod{19}$

we will multiply both sides by $5$. This gives

$20x\equiv 15 \pmod{19}$ - Step 1

But $20\equiv 1\pmod{19}$, so $20x\equiv x\pmod{19}$ - Step 2

Thus the solution is

$x\equiv 15\pmod{19}$

I understand up to step 2, I am unable to understand how one arrives at the solution from Step 2.

How does

$20x\equiv x \pmod{19}$
lead to
$x\equiv 15 \pmod{19}$

Where did the $20$ on the LHS go? How did $x$ on the RHS get replaced by $15$?

Martin Sleziak
  • 51,859
  • 20
  • 181
  • 357
user93353
  • 424
  • 2
  • 18
  • Do you understand why $20x\equiv x\pmod {19}$? – lulu Aug 19 '20 at 08:26
  • @lulu - I think yes. `20≡1(mod19)` is true. If you multiply both sides of that by `x`, you get `20x≡x(mod19)`. Is that correct or not? – user93353 Aug 19 '20 at 08:28
  • Yes, that's correct. So, then, start with the original, $4x\equiv 3 \pmod {19}$. Multiply both sides by $5$ to get $20x\equiv 15\pmod {19}$, right? But you already agreed that $20x\equiv x\pmod {19}$ so we must have $x\equiv 15\pmod {19}$. – lulu Aug 19 '20 at 08:30
  • @lulu `20x≡x(mod19)` so we must have `x≡15(mod19)` - As I said this is what I don't understand. If `20x≡x(mod19)` is true, how does that lead to `x≡15(mod19)` – user93353 Aug 19 '20 at 08:33
  • Just read my comment again, follow it step by step. Do you agree that $4x\equiv 3 \pmod {19}\implies 20x\equiv 15\pmod {19}$? – lulu Aug 19 '20 at 08:34
  • Some one else in one of the answers said that since gcd(5,19)=1 you are allowed to multiply both sides by 5. So I guess I agree to multiplying both sides by 5 & getting `20x≡15(mod19)` – user93353 Aug 19 '20 at 08:38
  • 1
    You could multiply both sides by $5$ regardless of the gcd condition. You need the gcd condition to divide by $5$, not multiply by it. – lulu Aug 19 '20 at 08:39
  • 1
    Regardless of that, though, look at what you have agreed to: You agreed that $20x\equiv x$ and that $20x\equiv 15$ (I'm dropping the $\pmod {19}'s$ to make the writing easier). But if $a=b$ and $a=c$ then $b=c$. – lulu Aug 19 '20 at 08:41
  • If you are just learning congruences, you may want to convince yourself that they really do satisfy the transitive property. That is: $a\equiv b\pmod {n}$ and $a\equiv c\pmod n$ imply that $b\equiv c\pmod {n}$. – lulu Aug 19 '20 at 08:45
  • I think I should pick up some new book. This is from Joseph Silverman's book on Number Theory & it doesn't mention Transitivity anywhere. Could you recommend a good beginner's book on number theory? – user93353 Aug 19 '20 at 08:52
  • If you could put your comments as an answer, including your comment with the transitivity example, I will accept it as an answer. Thank you for your help – user93353 Aug 19 '20 at 08:54
  • Joe's book is fine, I'm sure he goes through the basic properties of congruences. But you don't need a book for that, just write out the definitions: $a\equiv b \pmod n$ means that $(a-b)=rn$ for some integer $r$. That's the definition. Similarly $a\equiv c \pmod n$ means that $(a-c)=sn$ for some integer $s$. But then we can subtract to see that $(b-c)=(s-r)n$ so $b\equiv c \pmod n$. – lulu Aug 19 '20 at 08:55
  • He goes through the properties, yes. And I can understand your derivation of transitivity. But for a beginner like me, I wouldn't have assumed transitivity or even thought he is using it because he has never mentioned it anywhere. If this is a "Friendly introduction", I cannot imagine what an unfriendly introduction would be. Thank you for your help – user93353 Aug 19 '20 at 08:59
  • 1
    For another introduction, try [The Art of Problem Solving](https://artofproblemsolving.com/wiki/index.php/Modular_arithmetic/Introduction) – lulu Aug 19 '20 at 09:08
  • @lulu I looked at the ArtOfProblemSolving but that doesn't seem to mention Transitivity etc. Looks like all mathematicians think people already know this – user93353 Aug 19 '20 at 10:40
  • Perhaps it's not in the short account they posted online, but try their text [Introduction to Number Theory](https://artofproblemsolving.com/store/item/intro-number-theory?gtmlist=Bookstore_Home). Should say: I've loaned my copy out so I can't immediately confirm that this is stated explicitly there. – lulu Aug 19 '20 at 11:10

5 Answers5

5

I think the issue here concerns the basic properties of congruence.

In many important ways, congruence behaves exactly like equality. That is, it satisfies the three critical properties:

$1)$ Reflexive: $a\equiv a \pmod n$.

$2)$ Symmetric: $a\equiv b \pmod n\iff b\equiv a \pmod n$

$3)$ Transitive: $a\equiv b\pmod n$ and $b\equiv c\pmod n$ imply $a\equiv c \pmod n$.

Each of these follow easily from the core definition of congruence.

Those three properties, together, make congruence an Equivalence Relation. That's an important notion on its own..,in many ways, you can work with Equivalence Relations the same way you work with Equality. That's what is going on in the given calculation.

In this case you have $$20x\equiv x\pmod {19}\quad \&\quad 20x\equiv 15\pmod {19}$$ so combining the Symmetric Property and the Transitive Property get us $x\equiv {15}\pmod {19}$.

As usual, though, the important thing is the general principle. Those three properties are why congruences are so useful and important...make sure you understand why they hold.

lulu
  • 65,875
  • 4
  • 70
  • 119
  • As a side note, I will point out that using transitivity (and symmetry) we can also get from $x\equiv15\pmod{19}$ to $20x\equiv15\pmod{19}$. So altogether we have $20x\equiv15\pmod{19} \Longleftrightarrow x\equiv15\pmod{19}$. – Martin Sleziak Aug 19 '20 at 09:06
1

I will stress that $\gcd(5,19)=1$. Since $5$ is coprime to the modulus, multiplying by $5$ does not change the solutions so these two congruences are equivalent1

$$4x\equiv3\pmod{19} \Longleftrightarrow 20x\equiv15\pmod{19}$$

Now since $x\equiv20x\pmod{19}$, the latter is equivalent to $x\equiv15\pmod{19}$.

Since the comments here (and to the other answers) clarified that this is the main problem, let me spell the last equivalence in detail. (I will be freely using both symmetry and transitivity.)

  • $x\equiv20x\pmod{19}$ and $20x\equiv15\pmod{19}$ implies $x\equiv15\pmod{19}$
  • $20x\equiv x\pmod{19}$ $x\equiv15\pmod{19}$ implies $20x\equiv15\pmod{19}$
  • So we have both $$20x\equiv15\pmod{19} \Longrightarrow x\equiv15\pmod{19}$$ and $$x\equiv15\pmod{19} \Longrightarrow 20x\equiv15\pmod{19}$$ which gives us the equivalence $x\equiv15\pmod{19} \Longleftrightarrow 20x\equiv15\pmod{19}$.

1See, for example:

As a side note, I will mention that there exist chatrooms such as Number Theory and Basic Mathematics. And there is also the main chatroom for this site. See also: List of chatrooms. (I am mentioning this mainly since I saw that you had several exchanges in comments. If there are too many comments, that might be a sign that discussion in chat might be more suitable.)

Martin Sleziak
  • 51,859
  • 20
  • 181
  • 357
  • How does `x≡15(mod19)` follow from `x≡20x(mod19)`? – user93353 Aug 19 '20 at 08:37
  • @user93353 By transitivity: $a\equiv b\pmod n$ and $b\equiv c\pmod n$ implies $a\equiv c\pmod n$. In this case you have $x\equiv 20x$ and $20x\equiv15$, which gives $x\equiv15$. (And similarly you can show that $x\equiv15$ implies $20x\equiv15$.) – Martin Sleziak Aug 19 '20 at 08:42
  • This example is from Page 65 from Joseph Silverman's book on Number theory. I just searched the whole book for the word 'transi' and the search didn't get a single hit. I guess I should throw the book & try some other book – user93353 Aug 19 '20 at 08:48
  • Your example seems to be `a ≡ b (mod 19)` & `a ≡ c (mod 19)` & from there you go to `c ≡ b (mod 19)` - is that also true from transitivity? – user93353 Aug 19 '20 at 08:50
  • @user93353 I have checked Silverman: *"A friendly introduction to number theory* (4th edition) - but I do not see this on page 65. Did you mean some other book. (You should have included a more specific information about the book in the question.) Maybe you meant to write page 56? – Martin Sleziak Aug 19 '20 at 08:54
  • Sorry it's page 56 (Chapter 8) - The pdf page number was 65 – user93353 Aug 19 '20 at 08:55
  • If you have $a\equiv c$, then you have also $c\equiv a$. From $c\equiv a$ and $a\equiv b$ you get $c\equiv b$. (So we have used both transitivity and symmetry.) – Martin Sleziak Aug 19 '20 at 08:57
  • `Since 5 is coprime to the modulus, multiplying by 5 does not change the solutions so these two congruences are equivalent` - as per @lulu comment on my original question, they need to be coprime only to divide not to multiply – user93353 Aug 19 '20 at 10:30
  • @user93353 Yes, that's true. Still, the fact that they are coprime is still important if you want all solutions to the original problem about $4x\equiv3\pmod{19}$. (For example, it is easy to see that multiplying by $19$ would not give you and equivalent problem.) – Martin Sleziak Aug 19 '20 at 11:08
0

Well, $20\equiv 1 \mod 19$ and so $20\cdot x\equiv 1\cdot x\mod 19$.

The rest is how you explained it: Multiplying $4x\equiv 3\mod 19$ by $5$ on both sides gives $20x\equiv 15\mod 19$, i.e., $x\equiv 15\mod 19$.

Wuestenfux
  • 20,648
  • 2
  • 13
  • 24
  • Having the same problem with your answer also. I understand `20⋅x≡1⋅xmod19.` But I don't understand how the solution follows from that. I am missing something important - but I don't have a clue what it is? – user93353 Aug 19 '20 at 08:25
  • The rest is how you explained it. – Wuestenfux Aug 19 '20 at 08:31
  • I didn't explain anything as far as I know – user93353 Aug 19 '20 at 08:35
  • I understand this must be something very basic & simple for you, but this is my first attempt at Number theory & I am unable to understand. I am missing something basic, I guess – user93353 Aug 19 '20 at 08:35
  • The point is that the inverse of 4 mod 19 is 5, i.e., 4\cdot 5\equiv 1\mod 19$. This is the general approach ot solve such equations. – Wuestenfux Aug 19 '20 at 08:37
  • This example is from Page 65 of Joseph Silverman's Book on Number theory. There is no mention of "Inverse" before page 65. So I have no idea what is an inverse – user93353 Aug 19 '20 at 08:41
  • Sorry - it's from page 56, not 65 – user93353 Aug 19 '20 at 08:55
0

From here

$$20x\equiv 15 \mod19$$

we have that

$$20x=19x+x \implies 20x\equiv x \mod19$$

therefore

$$20x\equiv x\equiv 15 \mod19$$

Indeed by definition

$$a\equiv b \mod n \iff a-b=kn$$

therefore $20x\equiv x \mod 19 $ since $20x-x=19x$.

user
  • 148,135
  • 12
  • 74
  • 140
  • I am sorry - I just don't understand. I think I am missing something very basic in this - but I don't have a clue as to what it is. I understand `20x=19x+x`. I don't understand how the remaining this follow – user93353 Aug 19 '20 at 08:27
  • @user93353 By definition $x+19x\equiv x \mod 19$. – user Aug 19 '20 at 08:29
  • By what definition? – user93353 Aug 19 '20 at 08:32
  • Refer to [that](https://en.wikipedia.org/wiki/Modular_arithmetic). – user Aug 19 '20 at 08:33
  • What exactly in that. I am reading a book with a few chapters on congruences & I am unable to understand what in the definition I should look for – user93353 Aug 19 '20 at 08:34
  • Take a look to congruence, we define $a\equiv b \mod n \iff a-b=kn$ therefore $20x\equiv x \mod 19 $ since $20x-x=19x$. – user Aug 19 '20 at 08:40
0

ou can divide sides of relation resulted in step 1 be sides of relation resulted in step 2:

$\frac{20x}{20x} ≡ \frac {15} x \mod (19)$

⇒ $1 ≡ \frac {15} x \mod (19)$

⇒ $x ≡ 15 \mod (19)$

Martin Sleziak
  • 51,859
  • 20
  • 181
  • 357
sirous
  • 9,476
  • 3
  • 11
  • 22