How to factorize $a(y) := xy^3+xy^2+(x+1)y+x in GF(2)[x]_x^2+x+1[y]$

Clash Royale CLAN TAG#URR8PPP

up vote
1
down vote

favorite

Could someone please help me to find irreducible factors of $a(y) := xy^3+xy^2+(x+1)y+x in GF(2)[x]_x^2+x+1[y]$?

In $GF(2)[x]_x^2+x+1[y]$, we have $0,1,x,x+1$. So we use these in $a(y)$ one after the other:
$0:x⋅0^3+x⋅0^2+(x+1)⋅0+x=x$ => not a root
$1:x⋅1^3+x⋅1^2+(x+1)⋅1+x=x+x+x+1+x=4x+1=1$ => not a root
$x:x⋅x^3+x⋅x^2+(x+1)⋅x+x=x^4+x^3+x^2+x+x=x^4+x^3+x^2$

But I don't understand what should I do with $x^4+x^3+x^2$ now?
I can factorize it into $x^2⋅(x^2+x+1)$ but how can I understand that x is a root ot not?

Thank you for any help!

factoring

share|cite|improve this question

asked Jul 22 at 19:03

pramort

303

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Hint: $x^2$ is $x+1$, so mod $2$ we have $x^2+x+1$ equal zero (by construction).
  – hardmath
  Jul 22 at 19:21
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Does $GF(2)[x]_x^2+x+1$ denote $GF(2)[x]$ localised at the element $x^2+x+1$ or modulo $x^2+x+1$?
  – Bernard
  Jul 22 at 20:15
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  modulo $x^2+x+1$
  – pramort
  Jul 22 at 20:18
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @hardmath,thank you very much, I was able to understand the problem now.
  – pramort
  Jul 22 at 20:33
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I invite you to try your hand at posting the completed Answer, if you have the energy.
  – hardmath
  Jul 22 at 20:37
  

  
  
  
  

 | 
show 4 more comments

up vote
1
down vote

favorite

Could someone please help me to find irreducible factors of $a(y) := xy^3+xy^2+(x+1)y+x in GF(2)[x]_x^2+x+1[y]$?

In $GF(2)[x]_x^2+x+1[y]$, we have $0,1,x,x+1$. So we use these in $a(y)$ one after the other:
$0:x⋅0^3+x⋅0^2+(x+1)⋅0+x=x$ => not a root
$1:x⋅1^3+x⋅1^2+(x+1)⋅1+x=x+x+x+1+x=4x+1=1$ => not a root
$x:x⋅x^3+x⋅x^2+(x+1)⋅x+x=x^4+x^3+x^2+x+x=x^4+x^3+x^2$

But I don't understand what should I do with $x^4+x^3+x^2$ now?
I can factorize it into $x^2⋅(x^2+x+1)$ but how can I understand that x is a root ot not?

Thank you for any help!

factoring

share|cite|improve this question

asked Jul 22 at 19:03

pramort

303

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Hint: $x^2$ is $x+1$, so mod $2$ we have $x^2+x+1$ equal zero (by construction).
  – hardmath
  Jul 22 at 19:21
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Does $GF(2)[x]_x^2+x+1$ denote $GF(2)[x]$ localised at the element $x^2+x+1$ or modulo $x^2+x+1$?
  – Bernard
  Jul 22 at 20:15
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  modulo $x^2+x+1$
  – pramort
  Jul 22 at 20:18
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @hardmath,thank you very much, I was able to understand the problem now.
  – pramort
  Jul 22 at 20:33
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I invite you to try your hand at posting the completed Answer, if you have the energy.
  – hardmath
  Jul 22 at 20:37
  

  
  
  
  

 | 
show 4 more comments

up vote
1
down vote

favorite

up vote
1
down vote

favorite

Could someone please help me to find irreducible factors of $a(y) := xy^3+xy^2+(x+1)y+x in GF(2)[x]_x^2+x+1[y]$?

In $GF(2)[x]_x^2+x+1[y]$, we have $0,1,x,x+1$. So we use these in $a(y)$ one after the other:
$0:x⋅0^3+x⋅0^2+(x+1)⋅0+x=x$ => not a root
$1:x⋅1^3+x⋅1^2+(x+1)⋅1+x=x+x+x+1+x=4x+1=1$ => not a root
$x:x⋅x^3+x⋅x^2+(x+1)⋅x+x=x^4+x^3+x^2+x+x=x^4+x^3+x^2$

But I don't understand what should I do with $x^4+x^3+x^2$ now?
I can factorize it into $x^2⋅(x^2+x+1)$ but how can I understand that x is a root ot not?

Thank you for any help!

factoring

share|cite|improve this question

asked Jul 22 at 19:03

pramort

303

Could someone please help me to find irreducible factors of $a(y) := xy^3+xy^2+(x+1)y+x in GF(2)[x]_x^2+x+1[y]$?

In $GF(2)[x]_x^2+x+1[y]$, we have $0,1,x,x+1$. So we use these in $a(y)$ one after the other:
$0:x⋅0^3+x⋅0^2+(x+1)⋅0+x=x$ => not a root
$1:x⋅1^3+x⋅1^2+(x+1)⋅1+x=x+x+x+1+x=4x+1=1$ => not a root
$x:x⋅x^3+x⋅x^2+(x+1)⋅x+x=x^4+x^3+x^2+x+x=x^4+x^3+x^2$

But I don't understand what should I do with $x^4+x^3+x^2$ now?
I can factorize it into $x^2⋅(x^2+x+1)$ but how can I understand that x is a root ot not?

Thank you for any help!

factoring

share|cite|improve this question

asked Jul 22 at 19:03

pramort

303

share|cite|improve this question

share|cite|improve this question

asked Jul 22 at 19:03

pramort

303

asked Jul 22 at 19:03

pramort

303

asked Jul 22 at 19:03

pramort

303

303

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Hint: $x^2$ is $x+1$, so mod $2$ we have $x^2+x+1$ equal zero (by construction).
  – hardmath
  Jul 22 at 19:21
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Does $GF(2)[x]_x^2+x+1$ denote $GF(2)[x]$ localised at the element $x^2+x+1$ or modulo $x^2+x+1$?
  – Bernard
  Jul 22 at 20:15
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  modulo $x^2+x+1$
  – pramort
  Jul 22 at 20:18
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @hardmath,thank you very much, I was able to understand the problem now.
  – pramort
  Jul 22 at 20:33
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I invite you to try your hand at posting the completed Answer, if you have the energy.
  – hardmath
  Jul 22 at 20:37
  

  
  
  
  

 | 
show 4 more comments

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Hint: $x^2$ is $x+1$, so mod $2$ we have $x^2+x+1$ equal zero (by construction).
  – hardmath
  Jul 22 at 19:21
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Does $GF(2)[x]_x^2+x+1$ denote $GF(2)[x]$ localised at the element $x^2+x+1$ or modulo $x^2+x+1$?
  – Bernard
  Jul 22 at 20:15
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  modulo $x^2+x+1$
  – pramort
  Jul 22 at 20:18
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @hardmath,thank you very much, I was able to understand the problem now.
  – pramort
  Jul 22 at 20:33
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I invite you to try your hand at posting the completed Answer, if you have the energy.
  – hardmath
  Jul 22 at 20:37
  

  
  
  
  

1

1

Hint: $x^2$ is $x+1$, so mod $2$ we have $x^2+x+1$ equal zero (by construction).
– hardmath
Jul 22 at 19:21

Hint: $x^2$ is $x+1$, so mod $2$ we have $x^2+x+1$ equal zero (by construction).
– hardmath
Jul 22 at 19:21

Does $GF(2)[x]_x^2+x+1$ denote $GF(2)[x]$ localised at the element $x^2+x+1$ or modulo $x^2+x+1$?
– Bernard
Jul 22 at 20:15

Does $GF(2)[x]_x^2+x+1$ denote $GF(2)[x]$ localised at the element $x^2+x+1$ or modulo $x^2+x+1$?
– Bernard
Jul 22 at 20:15

modulo $x^2+x+1$
– pramort
Jul 22 at 20:18

modulo $x^2+x+1$
– pramort
Jul 22 at 20:18

@hardmath,thank you very much, I was able to understand the problem now.
– pramort
Jul 22 at 20:33

@hardmath,thank you very much, I was able to understand the problem now.
– pramort
Jul 22 at 20:33

I invite you to try your hand at posting the completed Answer, if you have the energy.
– hardmath
Jul 22 at 20:37

I invite you to try your hand at posting the completed Answer, if you have the energy.
– hardmath
Jul 22 at 20:37

 | 
show 4 more comments

1 Answer
1

active

oldest

votes

up vote
0
down vote

@hardmath, I'll try :-)

In $GF(2)[x]_x^2+x+1[y]$, we have $0,1,x,x+1$. So we use these in a(y) one after the other:

• $0:x⋅0^3+x⋅0^2+(x+1)⋅0+x=x$ => not a root.


• $1:x⋅1^3+x⋅1^2+(x+1)⋅1+x=x+x+x+1+x=4x+1=1$ => not a root.


• $x:x⋅x^3+x⋅x^2+(x+1)⋅x+x=x4+x3+x2+x+x=x4+x3+x2 =0$ => x is a root.


• $x+1:x⋅(x+1)^3+x⋅(x+1)^2+(x+1)⋅(x+1)+x=x+x+1+x+x=1$ => not a root.

Therefore, we know that $(y+x)$ is one of the factors.

$(xy^3+xy^2+(x+1)y+x):(y+x)=xy^2+y+1$

Again, we use $0,1,x,x+1$ in order to determine whether $xy^2+y+1$ is irreducible:

• $0:x⋅0^2+0+1=1$ => not a root.


• $1:x⋅1^2+1+1=x$ => not a root.


• $x:x⋅x^2+x+1=x^3+x+1=x$ => not a root.


• $x+1:x(x+1)^2+(x+1)+1=x(x^2+1)+x=x^2=1$ => not a root.

$xy^2+y+1$ has no roots, so it is irreducible over GF(2).

Therefore,
$xy^3+xy^2+(x+1)y+x=(y+x)⋅(xy^2+y+1)$

share|cite|improve this answer

answered Jul 23 at 10:22

pramort

303

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2859687%2fhow-to-factorize-ay-xy3xy2x1yx-in-gf2x-x2x1y%23new-answer', 'question_page');

);

Post as a guest

Name Email

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
0
down vote

@hardmath, I'll try :-)

In $GF(2)[x]_x^2+x+1[y]$, we have $0,1,x,x+1$. So we use these in a(y) one after the other:

• $0:x⋅0^3+x⋅0^2+(x+1)⋅0+x=x$ => not a root.


• $1:x⋅1^3+x⋅1^2+(x+1)⋅1+x=x+x+x+1+x=4x+1=1$ => not a root.


• $x:x⋅x^3+x⋅x^2+(x+1)⋅x+x=x4+x3+x2+x+x=x4+x3+x2 =0$ => x is a root.


• $x+1:x⋅(x+1)^3+x⋅(x+1)^2+(x+1)⋅(x+1)+x=x+x+1+x+x=1$ => not a root.

Therefore, we know that $(y+x)$ is one of the factors.

$(xy^3+xy^2+(x+1)y+x):(y+x)=xy^2+y+1$

Again, we use $0,1,x,x+1$ in order to determine whether $xy^2+y+1$ is irreducible:

• $0:x⋅0^2+0+1=1$ => not a root.


• $1:x⋅1^2+1+1=x$ => not a root.


• $x:x⋅x^2+x+1=x^3+x+1=x$ => not a root.


• $x+1:x(x+1)^2+(x+1)+1=x(x^2+1)+x=x^2=1$ => not a root.

$xy^2+y+1$ has no roots, so it is irreducible over GF(2).

Therefore,
$xy^3+xy^2+(x+1)y+x=(y+x)⋅(xy^2+y+1)$

share|cite|improve this answer

answered Jul 23 at 10:22

pramort

303

add a comment | 

up vote
0
down vote

@hardmath, I'll try :-)

In $GF(2)[x]_x^2+x+1[y]$, we have $0,1,x,x+1$. So we use these in a(y) one after the other:

• $0:x⋅0^3+x⋅0^2+(x+1)⋅0+x=x$ => not a root.


• $1:x⋅1^3+x⋅1^2+(x+1)⋅1+x=x+x+x+1+x=4x+1=1$ => not a root.


• $x:x⋅x^3+x⋅x^2+(x+1)⋅x+x=x4+x3+x2+x+x=x4+x3+x2 =0$ => x is a root.


• $x+1:x⋅(x+1)^3+x⋅(x+1)^2+(x+1)⋅(x+1)+x=x+x+1+x+x=1$ => not a root.

Therefore, we know that $(y+x)$ is one of the factors.

$(xy^3+xy^2+(x+1)y+x):(y+x)=xy^2+y+1$

Again, we use $0,1,x,x+1$ in order to determine whether $xy^2+y+1$ is irreducible:

• $0:x⋅0^2+0+1=1$ => not a root.


• $1:x⋅1^2+1+1=x$ => not a root.


• $x:x⋅x^2+x+1=x^3+x+1=x$ => not a root.


• $x+1:x(x+1)^2+(x+1)+1=x(x^2+1)+x=x^2=1$ => not a root.

$xy^2+y+1$ has no roots, so it is irreducible over GF(2).

Therefore,
$xy^3+xy^2+(x+1)y+x=(y+x)⋅(xy^2+y+1)$

share|cite|improve this answer

answered Jul 23 at 10:22

pramort

303

add a comment | 

up vote
0
down vote

up vote
0
down vote

@hardmath, I'll try :-)

In $GF(2)[x]_x^2+x+1[y]$, we have $0,1,x,x+1$. So we use these in a(y) one after the other:

• $0:x⋅0^3+x⋅0^2+(x+1)⋅0+x=x$ => not a root.


• $1:x⋅1^3+x⋅1^2+(x+1)⋅1+x=x+x+x+1+x=4x+1=1$ => not a root.


• $x:x⋅x^3+x⋅x^2+(x+1)⋅x+x=x4+x3+x2+x+x=x4+x3+x2 =0$ => x is a root.


• $x+1:x⋅(x+1)^3+x⋅(x+1)^2+(x+1)⋅(x+1)+x=x+x+1+x+x=1$ => not a root.

Therefore, we know that $(y+x)$ is one of the factors.

$(xy^3+xy^2+(x+1)y+x):(y+x)=xy^2+y+1$

Again, we use $0,1,x,x+1$ in order to determine whether $xy^2+y+1$ is irreducible:

• $0:x⋅0^2+0+1=1$ => not a root.


• $1:x⋅1^2+1+1=x$ => not a root.


• $x:x⋅x^2+x+1=x^3+x+1=x$ => not a root.


• $x+1:x(x+1)^2+(x+1)+1=x(x^2+1)+x=x^2=1$ => not a root.

$xy^2+y+1$ has no roots, so it is irreducible over GF(2).

Therefore,
$xy^3+xy^2+(x+1)y+x=(y+x)⋅(xy^2+y+1)$

share|cite|improve this answer

answered Jul 23 at 10:22

pramort

303

@hardmath, I'll try :-)

In $GF(2)[x]_x^2+x+1[y]$, we have $0,1,x,x+1$. So we use these in a(y) one after the other:

• $0:x⋅0^3+x⋅0^2+(x+1)⋅0+x=x$ => not a root.


• $1:x⋅1^3+x⋅1^2+(x+1)⋅1+x=x+x+x+1+x=4x+1=1$ => not a root.


• $x:x⋅x^3+x⋅x^2+(x+1)⋅x+x=x4+x3+x2+x+x=x4+x3+x2 =0$ => x is a root.


• $x+1:x⋅(x+1)^3+x⋅(x+1)^2+(x+1)⋅(x+1)+x=x+x+1+x+x=1$ => not a root.

Therefore, we know that $(y+x)$ is one of the factors.

$(xy^3+xy^2+(x+1)y+x):(y+x)=xy^2+y+1$

Again, we use $0,1,x,x+1$ in order to determine whether $xy^2+y+1$ is irreducible:

• $0:x⋅0^2+0+1=1$ => not a root.


• $1:x⋅1^2+1+1=x$ => not a root.


• $x:x⋅x^2+x+1=x^3+x+1=x$ => not a root.


• $x+1:x(x+1)^2+(x+1)+1=x(x^2+1)+x=x^2=1$ => not a root.

$xy^2+y+1$ has no roots, so it is irreducible over GF(2).

Therefore,
$xy^3+xy^2+(x+1)y+x=(y+x)⋅(xy^2+y+1)$

share|cite|improve this answer

answered Jul 23 at 10:22

pramort

303

share|cite|improve this answer

share|cite|improve this answer

answered Jul 23 at 10:22

pramort

303

answered Jul 23 at 10:22

pramort

303

answered Jul 23 at 10:22

pramort

303

303

add a comment | 

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2859687%2fhow-to-factorize-ay-xy3xy2x1yx-in-gf2x-x2x1y%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email