Mathematics desk
< October 29	<< Sep \| October \| Nov >>	Current desk >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 30

Roots of $X^{n{-}1}{+}1$ in $\mathbb {Z} /n$

Copied from WP:RD/MA/2020 October 22#Number of roots of polinomial in fields other than C. --Lambiam 14:58, 30 October 2020 (UTC)[reply]

Experimentally, it appears that the polynomial $X^{n{-}1}{+}1,$ $n>1,$ has roots in $\mathbb {Z} /n$ iff its degree $n{-}1$ is odd. In the latter case we always have the root $X=n{-}1,$ and usually this is the only root. But sometimes there are more: for example, $X^{27}{+}1$ has 3 roots in $\mathbb {Z} /28$ ( $X=3,$ $X=19,$ $X=27$ ), $X^{741}{+}1$ has 39 roots in $\mathbb {Z} /742,$ and $X^{945}{+}1$ has 105 roots in $\mathbb {Z} /946.$ I see no obvious pattern, but no doubt someone has studied this. --Lambiam 08:05, 27 October 2020 (UTC)[reply]

If $p$ is an odd prime, the absence of roots of $X^{p{-}1}{+}1$ in $\mathbb {Z} /p$ follows from Fermat's little theorem. For composite odd moduli, their absence remains unexplained. --Lambiam 17:50, 28 October 2020 (UTC)[reply]

The Chinese remainder theorem covers the case of products of distinct odd primes.--Jasper Deng (talk) 03:53, 29 October 2020 (UTC)[reply]

@JD — Can you give a proof sketch? I don't see the connection straightaway. I also remain curious about the odd distribution of the number of roots if the degree is odd. --Lambiam 15:05, 30 October 2020 (UTC)[reply]

If n is even then (-1)^n-1 = -1, and so X^n-1+1=0 has a solution. The number of solutions is a bit trickier to determine. Note that since the map X→X^a is an endomorphism of the multiplicative group mod n, the number of solutions to X^a=b is equal to either 0 or the order of the kernel of this endomorphism. The n odd case seems more difficult, but the structure of the multiplicative group mod n is well known and this information can be utilized to derive a contradiction if X^n-1=-1 has a solution mod n. There may be a more elementary proof but I didn't see one. I haven't completely checked the details, but I think you can go a bit further: If a is even, n odd, a = 2^αb where b is odd, then X^a=-1 has a solution mod n only if each prime dividing n is congruent to 1 mod 2^α+1. --RDBury (talk) 22:48, 30 October 2020 (UTC)[reply]

PS. OEIS: A063994 gives the number of solutions of X^n-1=1 (mod n). If n is even this is the same number of solutions as X^n-1=-1. An easy(er) way to see this is that X^n-1=1 iff (-X)^n-1=-1. The first even number for which this value is >1 is 28, then 52, 66, 70, 76, ... --RDBury (talk) 07:49, 31 October 2020 (UTC)[reply]

October 30

Roots of X n − 1 + 1 {\displaystyle X^{n{-}1}{+}1} in Z / n {\displaystyle \mathbb {Z} /n}

Roots of $X^{n{-}1}{+}1$ in $\mathbb {Z} /n$