Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm studying the remainder class $\mathbb{Z}_n$, I've grabbed something, but something else is unfocused. Let $$20x \equiv 4\pmod{34}$$ then GCD(20,34)=2 so I rewrite as: $$10x \equiv 2\pmod{17}$$ and successively: $$10x \equiv 1\pmod{17}$$ Now I know $\gcd(10, 17)=1$

Question 1: Why? Is this cause I've divided both $20$ and $34$ for the same $\gcd=2$? If $d$ is a $\gcd$ for $a$ and $b$, then $\gcd(a/d, b/d)=1$?

At this point I can: $$1=10\alpha + 17\beta$$ that will be: $$1=10(-5)+17\cdot 3$$

Question 2: I know that $-5$ is the solution of equation, but why I have to choose $-5$ more than $3$?

Now $-5$ is a solution for: $$10x \equiv 1\pmod{17}$$ and $-5\cdot2$ is a solution for: $$10x \equiv 2\pmod{17}$$ $[-10]_{17}$ is class, the entire set is $\{-10+17k: k\in\mathbb{Z}\}$.

Question 3: This set will contain all invertible elements. Right? Now If I took $[8]_{17}$ and $[7]_{17}$ why the class $[56]_{17}$ is not in the same class of $[1]_{17}$ since it is invertible, matter of fact, $\gcd(56,17)=1$? Is $\gcd(x,y)=1$ the only way to test if $[x]_y$ is invertible? I know that element $a$ was invertible if $ba=ab=1$, but this contradicts my knowledge.

share|improve this question
1  
It is quite confusing to use the same symbol $x$ to denote both a solution of $10x\equiv 2$ and a solution of the subproblem $10x \equiv 1$. Instead, use $y$ for the latter: if $10y\equiv 1$ then $10(2y)\equiv 2(10y) \equiv 2$ so $x = 2y$ is a solution of the first equation, i.e $y \equiv 10^{-1}$ so $x \equiv 2\cdot 10^{-1}\equiv 2y$. –  Bill Dubuque Mar 1 '12 at 15:40
    
Why 0% accept rate? You can always accept answers like this: cdn.sstatic.net/img/faq/faq-accept-answer.png –  user2468 Mar 1 '12 at 18:29

3 Answers 3

up vote 1 down vote accepted

It is certainly true that if $\gcd(a,b)=d$ then $\gcd(a/d,b/d)=1$.

It is hard to say much more about your calculations, since there was an early problem. (And, what is worse, you ended up with the correct answer despite the early error! That is discussed at the end of this post.)

It is certainly true that $20x\equiv 4\pmod{34}$ if and only if $10x\equiv 2\pmod{17}$. For a justification, note that $34$ divides $20x-4$ if and only if $17$ divides $10x-2$. Maybe this is not obvious to you, so we do details. Note that $34$ divides $20x-4$ if and only if for some integer $q$, we have $34q=20x-4$. This is the case if and only if $17q=10x-2$.

Since $2$ and $17$ are relatively prime, $10x\equiv 2\pmod {17}$ if and only if $5x\equiv 1 \pmod {17}$. That is where things started to go wrong, since you had $10x\equiv 1\pmod{17}$ instead.

You ask for justification for the step that led you to $10x \equiv 1 \pmod{17}$. One cannot give such a justification, because the step is not correct.

But as to the step that I used to get to $5x\equiv 1\pmod{17}$, this can be done.

For $10x\equiv 2 \pmod{17}$ if and only if $17$ divides $10x-2$, or equivalently if and only if $17$ divides $2(5x-1)$. Since $17$ and $2$ are relatively prime, $17$ divides $2(5x-1)$ if and only if $17$ divides $5x-1$. In congruence language that says $5x\equiv 1\pmod{17}$.

So we are trying to solve the congruence $5x\equiv 1\pmod{17}$. Now that you have the right congruence, you should be able to push the rest through.

For your Question $2$, you say, correctly, that if we are looking for a solution of $1=10\alpha+17\beta$, then $\alpha=-5$ (with $\beta=3$) is a solution. You ask why we have to take $-5$ "more than $3$." I interpret that as meaning why do we use $\alpha$, not $\beta$.

The answer is that from $1=(10)(-5)+ (17)(3)$ we can conclude that $17$ divides $(10)(-5)-1$, so $(10)(-5)\equiv 1 \pmod {17}$, which was what you wanted. (But it was not what you actually needed.) We actually don't care about the value of $\beta$, as long as it is an integer.

Back to solving the problem. We want to solve $5x\equiv 1 \pmod {17}$. So we try to come up with $\alpha$ and $\beta$ such that $5\alpha+17\beta=1$. Note that $\alpha=-10$, $\beta=3$ works. So the solution to our congruence is $x=-10$. Equivalently, and more simply, we can take $x=7$, since $7\equiv -10\pmod{17}$.

So the integers $x$ that satisfy our original congruence are all integers of the form $7+17k$, where $k$ ranges over all the integers.

An accident: You ended up with the solutions $-10+17k$, which is correct, and equivalent to the answer I arrived at. But this was because of two errors that cancelled. You wrote down the wrong congruence, $10x\equiv 1$ instead of $5x\equiv 1$. You noted the solution $-5$. Then you wrote that $-5\cdot 2$ is a solution of $10x\equiv 2\pmod {17}$. So you multiplied the right hand side by $2$, but not the left. This cancelled the error you had made earlier, when you wrote $10 x\equiv 1 \pmod{17}$ instead of $5x\equiv 1 \pmod {17}$.

You could deliberately make these cancelling errors part of your standard procedure, and always get the right answer. But you will lose contact with what is really going on.

share|improve this answer
    
The OP is not deducing $10x\equiv 2\ \Rightarrow\ 10x \equiv 1$. Rather, he is saying that the former can be solved using a solution $y$ of the latter, i.e. $ x \equiv 2\cdot 10^{-1}\equiv 2y,\:$ see what follows. The OP is using the variable $x$ as the unknown in all of his equations - which leads to confusion. –  Bill Dubuque Mar 1 '12 at 15:19

You did all the right steps and got the right answer, but the way you wrote it is wrong and could cause confusion. You shouldn't use the same variable $x$ in $10x \equiv 2 \pmod{17}$ and $10x \equiv 1 \pmod{17}$, since these are completely different congruences.

The basic steps for doing arithmetic in $\mathbb{Z}_n$ are essentially the same as the steps you already know well for solving equations with real numbers. If you had the equation $$20x=4$$ over the real numbers, you would just divide both sides by 20 to get $$x=\frac{4}{20} = \frac{1}{5}.$$ In fact, what you're really doing is multiplying by the inverse of 20, which in the real numbers is $\frac{1}{20}$ since $20\cdot \frac{1}{20}=1$ in the real numbers.

If 20 were invertible in $\mathbb{Z}_{34}$, you could multiply both sides of the equation by the inverse of 20 in $\mathbb{Z}_{34}$ to get the answer-- but it's not invertible. To address this, we divide everything by the gcd of 20 and 34. As you seem to know already, this gives us $$10x \equiv 2 \pmod{17}.$$ If $d=\rm{gcd}(a,b)$, then $\rm{gcd}\left(\frac{a}{d},\frac{b}{d}\right)=1$. One good way to understand this is that $d$ represents everything $a$ and $b$ have in common, so that when we divide by $d$, there are no common factors left other than 1. Notice that this is exactly what we need: now we know that 10 is invertible in $\mathbb{Z}_{17}$, so we can multiply both sides by the inverse of 10 in $\mathbb{Z}_{17}$ (which is represented by -5) to get $$x \equiv -10 \pmod{17}.$$ The left side is just $x$ because $-5 \cdot 10 \equiv 1 \pmod{17}$. So $x \equiv -10 \pmod{17}$ is the final answer!

Of course, a big part of the work is finding the inverse of 10 in $\mathbb{Z}_{17}$. That's where your other equation comes in, where you shouldn't use $x$. Let's use $\alpha$ instead: $$10 \alpha \equiv 1 \pmod{17}.$$ Solving this is exactly the same as finding an integer solution to $$10\alpha +17 \beta =1,$$ except that we don't care what $\beta$ is, since we only want $\alpha$, which is the inverse to 10 in $\mathbb{Z}_{17}$. (Actually, $\beta$ represents an inverse to 17 in $\mathbb{Z}_{10}$, which could be useful in another problem, but is not useful in this problem.)

You correctly solved this and got $\alpha=-5$, but any element of the class $[-5]_{17}$ is a valid solution and is the inverse to 10 in $\mathbb{Z}_{17}$. What this means is that you can take any element of the class $[-5]_{17}$ and multiply it by any element of the class $[10]_{17}$, and you will get a number that is in the class $[1]_{17}$. (I don't know where the 8 comes from in your last question, but the reason it doesn't work as you want is that 8 isn't from the right class in $\mathbb{Z}_{17}$.) For example, I can take 12 from $[-5]_{17}$ and 27 from $[10]_{17}$; their product is 324, which is equal to $19\cdot 17 +1$.

share|improve this answer

For question $1$, one has in fact for any common (positive) divisor $d$ of $a$ and $b$ that $\gcd(a/d,b/d)=\gcd(a,b)/d$, which gives your equation for the case $d=\gcd(a,b)$. Questions $2$ and $3$ are somewhat confused. Before question $2$ you replaced a congruence $10x\equiv2$ by an inequivalent one $10x\equiv1$; maybe you meant $5x\equiv 1$? If question $2$ concerns why you are interested in the Bezout coefficient $-5$ rather than in the other one $3$, then the answer is that your original question was a congruence modulo $17$, so the Bezout coefficient by which $17$ is multiplied does not interest you. In fact it is not necessary to consider that Bezout coefficient at all: you can save half of the work in the extended Euclidean algorithm by not computing it in the first place (the computation of both Bezout coefficients is entirely independent, and in many application such as here one only needs one of them). As for question $3$, the class $[-10]_{17}$ is just one of the classes modulo $17$; it happens to be invertible, but by no means exhausts the invertible classes (there are $16$ different invertible classes modulo $17$). I'll add that while the class $[-10]_{17}$ is invertible in $\mathbb Z/17\mathbb Z$, none of its elements are invertible at all (in $\mathbb Z$, which is where they live).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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