How to solve systems of linear equations over a finite ring [closed]
$begingroup$
I don't know where to start and how to go forth when solving system of equations in for example $mathbb{Z}_{11}$. I have 2 different systems I want help with with a walkthrough to understand what is going on.
System 1:
begin{align}4x + 7y &= 3 pmod {11}\
8x + 5y& = 9 pmod {11}end{align}
System 2:
begin{align}3x + y + z &= 1 pmod {11}\
5x + y - z &= 2 pmod{11}\
2x - y - z &= 1 pmod {11}end{align}
finite-rings
edited Jan 11 at 14:35
lioness99a
3,9012727
asked Jan 11 at 14:17
user633788user633788
63
$endgroup$
closed as off-topic by Namaste, A. Pongrácz, Dave, Lord_Farin, Did Jan 11 at 20:19
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Namaste, A. Pongrácz, Dave, Lord_Farin, Did
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
I don't know where to start and how to go forth when solving system of equations in for example $mathbb{Z}_{11}$. I have 2 different systems I want help with with a walkthrough to understand what is going on.
System 1:
begin{align}4x + 7y &= 3 pmod {11}\
8x + 5y& = 9 pmod {11}end{align}
System 2:
begin{align}3x + y + z &= 1 pmod {11}\
5x + y - z &= 2 pmod{11}\
2x - y - z &= 1 pmod {11}end{align}
finite-rings
edited Jan 11 at 14:35
lioness99a
3,9012727
asked Jan 11 at 14:17
user633788user633788
63
$endgroup$
closed as off-topic by Namaste, A. Pongrácz, Dave, Lord_Farin, Did Jan 11 at 20:19
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Namaste, A. Pongrácz, Dave, Lord_Farin, Did
If this question can be reworded to fit the rules in the help center, please edit the question.
$begingroup$
In the same way if you work over the real numbers. In ${Bbb Z}_{11}$ each element has an additive inverse and each nonzero element has a multiplicative inverse.
$endgroup$
– Wuestenfux
Jan 11 at 14:23
$begingroup$
Note: as $11$ is prime, your ring is a field. You can perform division without shame
$endgroup$
– Damien
Jan 11 at 14:25
add a comment |
$begingroup$
I don't know where to start and how to go forth when solving system of equations in for example $mathbb{Z}_{11}$. I have 2 different systems I want help with with a walkthrough to understand what is going on.
System 1:
begin{align}4x + 7y &= 3 pmod {11}\
8x + 5y& = 9 pmod {11}end{align}
System 2:
begin{align}3x + y + z &= 1 pmod {11}\
5x + y - z &= 2 pmod{11}\
2x - y - z &= 1 pmod {11}end{align}
finite-rings
edited Jan 11 at 14:35
lioness99a
3,9012727
asked Jan 11 at 14:17
user633788user633788
63
$endgroup$
I don't know where to start and how to go forth when solving system of equations in for example $mathbb{Z}_{11}$. I have 2 different systems I want help with with a walkthrough to understand what is going on.
System 1:
begin{align}4x + 7y &= 3 pmod {11}\
8x + 5y& = 9 pmod {11}end{align}
System 2:
begin{align}3x + y + z &= 1 pmod {11}\
5x + y - z &= 2 pmod{11}\
2x - y - z &= 1 pmod {11}end{align}
finite-rings
finite-rings
edited Jan 11 at 14:35
lioness99a
3,9012727
asked Jan 11 at 14:17
user633788user633788
63
edited Jan 11 at 14:35
lioness99a
3,9012727
asked Jan 11 at 14:17
user633788user633788
63
edited Jan 11 at 14:35
lioness99a
3,9012727
edited Jan 11 at 14:35
lioness99a
3,9012727
edited Jan 11 at 14:35
lioness99a
3,9012727
3,9012727
asked Jan 11 at 14:17
user633788user633788
63
asked Jan 11 at 14:17
user633788user633788
63
asked Jan 11 at 14:17
user633788user633788
63
63
closed as off-topic by Namaste, A. Pongrácz, Dave, Lord_Farin, Did Jan 11 at 20:19
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Namaste, A. Pongrácz, Dave, Lord_Farin, Did
If this question can be reworded to fit the rules in the help center, please edit the question.
closed as off-topic by Namaste, A. Pongrácz, Dave, Lord_Farin, Did Jan 11 at 20:19
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Namaste, A. Pongrácz, Dave, Lord_Farin, Did
If this question can be reworded to fit the rules in the help center, please edit the question.
$begingroup$
In the same way if you work over the real numbers. In ${Bbb Z}_{11}$ each element has an additive inverse and each nonzero element has a multiplicative inverse.
$endgroup$
– Wuestenfux
Jan 11 at 14:23
$begingroup$
Note: as $11$ is prime, your ring is a field. You can perform division without shame
$endgroup$
– Damien
Jan 11 at 14:25
add a comment |
$begingroup$
In the same way if you work over the real numbers. In ${Bbb Z}_{11}$ each element has an additive inverse and each nonzero element has a multiplicative inverse.
$endgroup$
– Wuestenfux
Jan 11 at 14:23
$begingroup$
Note: as $11$ is prime, your ring is a field. You can perform division without shame
$endgroup$
– Damien
Jan 11 at 14:25
$begingroup$
In the same way if you work over the real numbers. In ${Bbb Z}_{11}$ each element has an additive inverse and each nonzero element has a multiplicative inverse.
$endgroup$
– Wuestenfux
Jan 11 at 14:23
$begingroup$
In the same way if you work over the real numbers. In ${Bbb Z}_{11}$ each element has an additive inverse and each nonzero element has a multiplicative inverse.
$endgroup$
– Wuestenfux
Jan 11 at 14:23
$begingroup$
Note: as $11$ is prime, your ring is a field. You can perform division without shame
$endgroup$
– Damien
Jan 11 at 14:25
$begingroup$
Note: as $11$ is prime, your ring is a field. You can perform division without shame
$endgroup$
– Damien
Jan 11 at 14:25
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
To expand slightly on a previous answer, you have
begin{align}4x+7y&=3pmod {11}tag{1}\
8x+5y&=9pmod {11}tag{2}end{align}
As with regular simultaneous equations, we want to multiply $(1)$ by $2$ so we have an $8x$ in both equations:
begin{align}2times (4x+7y)&=2times3\
8x+14y&=6end{align}
However, this gives us $14y$ which we cannot have as we are working in $mathbb{Z}_{11}$. However, $$14pmod{11}=3$$ so instead we can write $$8x+3y=6tag{$(3)=(1)times 2$}$$
Now we can do $(2)-(3)$ to get
begin{align}(8x+5y)-(8x+3y)&=9-6\
8x-8x+5y-3y&=3\
2y&=3end{align}
We cannot simply say that $y=frac 32$ as we cannot have fractions in $mathbb {Z}_{11}$, but we know that, as $11$ is prime, each element will have a multiplicative inverse, and so we can find that $y=7$ as begin{align}2y&=2times 7\
&=14\
&=3pmod{11}end{align}
We can then substitute this value into $(2)$ to get begin{align}8x+5y&=9\
8x+5times 7&=9\
8x+35&=9\
8x+2&=9tag{*}\
8x&=7end{align}
$(*)$ We replace the $35$ with $2$ because $35pmod{11}=2$
Once again, we know that $x=5$ because begin{align}8x &= 8times 5\
&=40\
&=7pmod{11}end{align}
Therefore, the solution to our simultaneous equations is $x=5, y=7$. We can check this in $(1)$:
begin{align}4x+7y&=4times 5+7times 7\
&= 20 + 49\
&= 69\
&= 3pmod {11}end{align}
answered Jan 11 at 14:56
lioness99alioness99a
3,9012727
$endgroup$
add a comment |
$begingroup$
What's peculiar about $mathbb{Z}_{11}$? You do it is you would do it over any other field. Consider the first system:$$left{begin{array}{l}4x+7y=3\8x+5y=9.end{array}right.$$First step: you divide the first equation by $4$. Since we're working over $mathbb{Z}_{11}$ here, that's the same thing as multiplying by $3$, thereby getting$$left{begin{array}{l}x+10y=9\8x+5y=9.end{array}right.$$Now, you subtract from the second equation the first one times $8$ (which is the coefficient of $x$ from the second equation):$$left{begin{array}{l}x+10y=9\2y=3.end{array}right.$$Now you know that $y=7$ and so $x=cdots$
Can you solve the other system now?
answered Jan 11 at 14:23
José Carlos SantosJosé Carlos Santos
174k23133242
$endgroup$
$begingroup$
As 11 in Z11 is a prime, would it be any difference if it's in Z16?
$endgroup$
– user633788
Jan 11 at 14:47
$begingroup$
Yes, since $mathbb{Z}_{16}$ is not a field. Not all non-zero elements have an inverse.
$endgroup$
– José Carlos Santos
Jan 11 at 14:48
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
To expand slightly on a previous answer, you have
begin{align}4x+7y&=3pmod {11}tag{1}\
8x+5y&=9pmod {11}tag{2}end{align}
As with regular simultaneous equations, we want to multiply $(1)$ by $2$ so we have an $8x$ in both equations:
begin{align}2times (4x+7y)&=2times3\
8x+14y&=6end{align}
However, this gives us $14y$ which we cannot have as we are working in $mathbb{Z}_{11}$. However, $$14pmod{11}=3$$ so instead we can write $$8x+3y=6tag{$(3)=(1)times 2$}$$
Now we can do $(2)-(3)$ to get
begin{align}(8x+5y)-(8x+3y)&=9-6\
8x-8x+5y-3y&=3\
2y&=3end{align}
We cannot simply say that $y=frac 32$ as we cannot have fractions in $mathbb {Z}_{11}$, but we know that, as $11$ is prime, each element will have a multiplicative inverse, and so we can find that $y=7$ as begin{align}2y&=2times 7\
&=14\
&=3pmod{11}end{align}
We can then substitute this value into $(2)$ to get begin{align}8x+5y&=9\
8x+5times 7&=9\
8x+35&=9\
8x+2&=9tag{*}\
8x&=7end{align}
$(*)$ We replace the $35$ with $2$ because $35pmod{11}=2$
Once again, we know that $x=5$ because begin{align}8x &= 8times 5\
&=40\
&=7pmod{11}end{align}
Therefore, the solution to our simultaneous equations is $x=5, y=7$. We can check this in $(1)$:
begin{align}4x+7y&=4times 5+7times 7\
&= 20 + 49\
&= 69\
&= 3pmod {11}end{align}
answered Jan 11 at 14:56
lioness99alioness99a
3,9012727
$endgroup$
add a comment |
$begingroup$
To expand slightly on a previous answer, you have
begin{align}4x+7y&=3pmod {11}tag{1}\
8x+5y&=9pmod {11}tag{2}end{align}
As with regular simultaneous equations, we want to multiply $(1)$ by $2$ so we have an $8x$ in both equations:
begin{align}2times (4x+7y)&=2times3\
8x+14y&=6end{align}
However, this gives us $14y$ which we cannot have as we are working in $mathbb{Z}_{11}$. However, $$14pmod{11}=3$$ so instead we can write $$8x+3y=6tag{$(3)=(1)times 2$}$$
Now we can do $(2)-(3)$ to get
begin{align}(8x+5y)-(8x+3y)&=9-6\
8x-8x+5y-3y&=3\
2y&=3end{align}
We cannot simply say that $y=frac 32$ as we cannot have fractions in $mathbb {Z}_{11}$, but we know that, as $11$ is prime, each element will have a multiplicative inverse, and so we can find that $y=7$ as begin{align}2y&=2times 7\
&=14\
&=3pmod{11}end{align}
We can then substitute this value into $(2)$ to get begin{align}8x+5y&=9\
8x+5times 7&=9\
8x+35&=9\
8x+2&=9tag{*}\
8x&=7end{align}
$(*)$ We replace the $35$ with $2$ because $35pmod{11}=2$
Once again, we know that $x=5$ because begin{align}8x &= 8times 5\
&=40\
&=7pmod{11}end{align}
Therefore, the solution to our simultaneous equations is $x=5, y=7$. We can check this in $(1)$:
begin{align}4x+7y&=4times 5+7times 7\
&= 20 + 49\
&= 69\
&= 3pmod {11}end{align}
answered Jan 11 at 14:56
lioness99alioness99a
3,9012727
$endgroup$
add a comment |
$begingroup$
To expand slightly on a previous answer, you have
begin{align}4x+7y&=3pmod {11}tag{1}\
8x+5y&=9pmod {11}tag{2}end{align}
As with regular simultaneous equations, we want to multiply $(1)$ by $2$ so we have an $8x$ in both equations:
begin{align}2times (4x+7y)&=2times3\
8x+14y&=6end{align}
However, this gives us $14y$ which we cannot have as we are working in $mathbb{Z}_{11}$. However, $$14pmod{11}=3$$ so instead we can write $$8x+3y=6tag{$(3)=(1)times 2$}$$
Now we can do $(2)-(3)$ to get
begin{align}(8x+5y)-(8x+3y)&=9-6\
8x-8x+5y-3y&=3\
2y&=3end{align}
We cannot simply say that $y=frac 32$ as we cannot have fractions in $mathbb {Z}_{11}$, but we know that, as $11$ is prime, each element will have a multiplicative inverse, and so we can find that $y=7$ as begin{align}2y&=2times 7\
&=14\
&=3pmod{11}end{align}
We can then substitute this value into $(2)$ to get begin{align}8x+5y&=9\
8x+5times 7&=9\
8x+35&=9\
8x+2&=9tag{*}\
8x&=7end{align}
$(*)$ We replace the $35$ with $2$ because $35pmod{11}=2$
Once again, we know that $x=5$ because begin{align}8x &= 8times 5\
&=40\
&=7pmod{11}end{align}
Therefore, the solution to our simultaneous equations is $x=5, y=7$. We can check this in $(1)$:
begin{align}4x+7y&=4times 5+7times 7\
&= 20 + 49\
&= 69\
&= 3pmod {11}end{align}
answered Jan 11 at 14:56
lioness99alioness99a
3,9012727
$endgroup$
To expand slightly on a previous answer, you have
begin{align}4x+7y&=3pmod {11}tag{1}\
8x+5y&=9pmod {11}tag{2}end{align}
As with regular simultaneous equations, we want to multiply $(1)$ by $2$ so we have an $8x$ in both equations:
begin{align}2times (4x+7y)&=2times3\
8x+14y&=6end{align}
However, this gives us $14y$ which we cannot have as we are working in $mathbb{Z}_{11}$. However, $$14pmod{11}=3$$ so instead we can write $$8x+3y=6tag{$(3)=(1)times 2$}$$
Now we can do $(2)-(3)$ to get
begin{align}(8x+5y)-(8x+3y)&=9-6\
8x-8x+5y-3y&=3\
2y&=3end{align}
We cannot simply say that $y=frac 32$ as we cannot have fractions in $mathbb {Z}_{11}$, but we know that, as $11$ is prime, each element will have a multiplicative inverse, and so we can find that $y=7$ as begin{align}2y&=2times 7\
&=14\
&=3pmod{11}end{align}
We can then substitute this value into $(2)$ to get begin{align}8x+5y&=9\
8x+5times 7&=9\
8x+35&=9\
8x+2&=9tag{*}\
8x&=7end{align}
$(*)$ We replace the $35$ with $2$ because $35pmod{11}=2$
Once again, we know that $x=5$ because begin{align}8x &= 8times 5\
&=40\
&=7pmod{11}end{align}
Therefore, the solution to our simultaneous equations is $x=5, y=7$. We can check this in $(1)$:
begin{align}4x+7y&=4times 5+7times 7\
&= 20 + 49\
&= 69\
&= 3pmod {11}end{align}
answered Jan 11 at 14:56
lioness99alioness99a
3,9012727
edited Jan 11 at 15:11
answered Jan 11 at 14:56
lioness99alioness99a
3,9012727
answered Jan 11 at 14:56
lioness99alioness99a
3,9012727
answered Jan 11 at 14:56
lioness99alioness99a
3,9012727
3,9012727
add a comment |
add a comment |
$begingroup$
What's peculiar about $mathbb{Z}_{11}$? You do it is you would do it over any other field. Consider the first system:$$left{begin{array}{l}4x+7y=3\8x+5y=9.end{array}right.$$First step: you divide the first equation by $4$. Since we're working over $mathbb{Z}_{11}$ here, that's the same thing as multiplying by $3$, thereby getting$$left{begin{array}{l}x+10y=9\8x+5y=9.end{array}right.$$Now, you subtract from the second equation the first one times $8$ (which is the coefficient of $x$ from the second equation):$$left{begin{array}{l}x+10y=9\2y=3.end{array}right.$$Now you know that $y=7$ and so $x=cdots$
Can you solve the other system now?
answered Jan 11 at 14:23
José Carlos SantosJosé Carlos Santos
174k23133242
$endgroup$
$begingroup$
As 11 in Z11 is a prime, would it be any difference if it's in Z16?
$endgroup$
– user633788
Jan 11 at 14:47
$begingroup$
Yes, since $mathbb{Z}_{16}$ is not a field. Not all non-zero elements have an inverse.
$endgroup$
– José Carlos Santos
Jan 11 at 14:48
add a comment |
$begingroup$
What's peculiar about $mathbb{Z}_{11}$? You do it is you would do it over any other field. Consider the first system:$$left{begin{array}{l}4x+7y=3\8x+5y=9.end{array}right.$$First step: you divide the first equation by $4$. Since we're working over $mathbb{Z}_{11}$ here, that's the same thing as multiplying by $3$, thereby getting$$left{begin{array}{l}x+10y=9\8x+5y=9.end{array}right.$$Now, you subtract from the second equation the first one times $8$ (which is the coefficient of $x$ from the second equation):$$left{begin{array}{l}x+10y=9\2y=3.end{array}right.$$Now you know that $y=7$ and so $x=cdots$
Can you solve the other system now?
answered Jan 11 at 14:23
José Carlos SantosJosé Carlos Santos
174k23133242
$endgroup$
$begingroup$
As 11 in Z11 is a prime, would it be any difference if it's in Z16?
$endgroup$
– user633788
Jan 11 at 14:47
$begingroup$
Yes, since $mathbb{Z}_{16}$ is not a field. Not all non-zero elements have an inverse.
$endgroup$
– José Carlos Santos
Jan 11 at 14:48
add a comment |
$begingroup$
What's peculiar about $mathbb{Z}_{11}$? You do it is you would do it over any other field. Consider the first system:$$left{begin{array}{l}4x+7y=3\8x+5y=9.end{array}right.$$First step: you divide the first equation by $4$. Since we're working over $mathbb{Z}_{11}$ here, that's the same thing as multiplying by $3$, thereby getting$$left{begin{array}{l}x+10y=9\8x+5y=9.end{array}right.$$Now, you subtract from the second equation the first one times $8$ (which is the coefficient of $x$ from the second equation):$$left{begin{array}{l}x+10y=9\2y=3.end{array}right.$$Now you know that $y=7$ and so $x=cdots$
Can you solve the other system now?
answered Jan 11 at 14:23
José Carlos SantosJosé Carlos Santos
174k23133242
$endgroup$
What's peculiar about $mathbb{Z}_{11}$? You do it is you would do it over any other field. Consider the first system:$$left{begin{array}{l}4x+7y=3\8x+5y=9.end{array}right.$$First step: you divide the first equation by $4$. Since we're working over $mathbb{Z}_{11}$ here, that's the same thing as multiplying by $3$, thereby getting$$left{begin{array}{l}x+10y=9\8x+5y=9.end{array}right.$$Now, you subtract from the second equation the first one times $8$ (which is the coefficient of $x$ from the second equation):$$left{begin{array}{l}x+10y=9\2y=3.end{array}right.$$Now you know that $y=7$ and so $x=cdots$
Can you solve the other system now?
answered Jan 11 at 14:23
José Carlos SantosJosé Carlos Santos
174k23133242
answered Jan 11 at 14:23
José Carlos SantosJosé Carlos Santos
174k23133242
answered Jan 11 at 14:23
José Carlos SantosJosé Carlos Santos
174k23133242
answered Jan 11 at 14:23
José Carlos SantosJosé Carlos Santos
174k23133242
174k23133242
$begingroup$
As 11 in Z11 is a prime, would it be any difference if it's in Z16?
$endgroup$
– user633788
Jan 11 at 14:47
$begingroup$
Yes, since $mathbb{Z}_{16}$ is not a field. Not all non-zero elements have an inverse.
$endgroup$
– José Carlos Santos
Jan 11 at 14:48
add a comment |
$begingroup$
As 11 in Z11 is a prime, would it be any difference if it's in Z16?
$endgroup$
– user633788
Jan 11 at 14:47
$begingroup$
Yes, since $mathbb{Z}_{16}$ is not a field. Not all non-zero elements have an inverse.
$endgroup$
– José Carlos Santos
Jan 11 at 14:48
$begingroup$
As 11 in Z11 is a prime, would it be any difference if it's in Z16?
$endgroup$
– user633788
Jan 11 at 14:47
$begingroup$
As 11 in Z11 is a prime, would it be any difference if it's in Z16?
$endgroup$
– user633788
Jan 11 at 14:47
$begingroup$
Yes, since $mathbb{Z}_{16}$ is not a field. Not all non-zero elements have an inverse.
$endgroup$
– José Carlos Santos
Jan 11 at 14:48
$begingroup$
Yes, since $mathbb{Z}_{16}$ is not a field. Not all non-zero elements have an inverse.
$endgroup$
– José Carlos Santos
Jan 11 at 14:48
add a comment |
$begingroup$
In the same way if you work over the real numbers. In ${Bbb Z}_{11}$ each element has an additive inverse and each nonzero element has a multiplicative inverse.
$endgroup$
– Wuestenfux
Jan 11 at 14:23
$begingroup$
Note: as $11$ is prime, your ring is a field. You can perform division without shame
$endgroup$
– Damien
Jan 11 at 14:25