Question

Prove(x^d) -1 is a factor of x^(p-1)-1 if and only if d is a factor of  of p-1

Answer 1

Instead of p-1 ,  I will write   p.    So we have to prove iff  d is a factor of p, then (x^d -1) is a factor of (x^p - 1).

Let p = k d + c        where k and c are integers and  c < d  and is the remainder when p is divided by d.

Let us divide x^(kd+c) - 1 by x^d - 1

$x^d-1\ )\ x^{k d +c }\ -1\ \ \ \ (\ \ x^{(k-1)d+c}\\.\ \ \ \ \ \ \ \ \ \ x^{kd+c}-x^{(k-1)d+c}\\.\ \ \ \ \ \ \ \ =========\\.\ \ \ \ \ \ \ \ \ \ x^{(k-1)d+c}-1$

Thus each step in the polynomial division by (x^d-1) , we get a reminder which has a degree less by d.  Finally after k successive division steps, we get the quotient as :

$x^{(k-1)d+c}+x^{(k-2)d+c}+x^{(k-3)d+c}+....+x^{d+c}+x^c\\\\Remainder\ at\ this\ step\ is:\ (x^c-1)\\\\ ie.,\ x^p-1=(x^d-1)[x^{(k-1)d+c}+x^{(k-2)d+c}+....+x^{d+c}]+(x^c-1)\\\\For\ x^p-1\ to\ be\ divisible\ by\ x^d-1,\ c\ must\ be=0$

If c= 0,  p =  k d  =>  p is divisible by d.

This is the proof for  IF and ONLY IF parts both.