Divison of same degree polynomials Mod 3 - Euclidean Algorithm

Question

I have a question that I am looking for some help on.

I have two polynomials $f(x)$ and $g(x)$ and I am looking to find the $gcd(f(x),g(x))$ where the coefficients are reduced in modulo 3. In my case, $f(x)$ and $g(x)$ both are degree 4.

I have the form of $f(x)=q_1 g(x) + remainder$

However, when I do the algorithm at some point I get $q_2$ to contain a coefficient $1/2$ which does not belong to modulo 3 so I am unclear on what to do.

I can give the polynomials in the comment section if needs be as I am looking for guidance rather than solutions

Thanks in advance!

Hint: $\frac{1}{2}=2^{-1}$ – Alberto Andrenucci Mar 19 '17 at 20:19 — Alberto Andrenucci, Mar 19 '17 at 20:19

score 1 · Answer 1 · answered Mar 19 '17 at 20:18

1

Hint: Use the fact that the inverse of $2$ mod $3$ is $2$ mod $3$ (since $2.2=4=1$ mod 3) and not $1/2$ and replace $1/2$ by $2$ in the expression of $q_2$.

answered Mar 19 '17 at 20:18

Tsemo Aristide

87,475

Okay so I can simply replace 1/2 by 2 because of the reasoning above? – ptsgeeg Mar 19 '17 at 20:26
yes, you have to divide in $\mathbb{Z}$ not in $\mathbb{Q}$. – Tsemo Aristide Mar 19 '17 at 20:27
That makes sense, thanks for your help ! – ptsgeeg Mar 19 '17 at 20:31
Just one more question, how is 2^-1 mod 3 equal to 2 mod 3? Is it something to do with the power? – ptsgeeg Mar 19 '17 at 20:36
no, because $2.2=4$ so ($2$ mod 3).(2 mod 3)= 4 mod 3 = 1 mod 3. – Tsemo Aristide Mar 19 '17 at 20:37
sorry for the confusion, but where has 2.2 come from? – ptsgeeg Mar 19 '17 at 20:41
You want to compute the inverse, of 2 mod 3 so (2 mod 3).(2 mod 3)= (2.2 mod 3)= (4 mod 3) – Tsemo Aristide Mar 19 '17 at 20:42
oh yes! Thanks for your help and patience! :) – ptsgeeg Mar 19 '17 at 20:45

Divison of same degree polynomials Mod 3 - Euclidean Algorithm

1 Answers1