[seqfan] Re: nth cyclotomic polynomial values modulo n

[israel at math.ubc.ca]

I'm not a real Number Theorist, but here's a bit of a start at explaining 
where all those 1's come from.

Suppose gcd(p,m) = 1, and let n = p^k m with k >= 1.  Then

C_n(X) = C_m(X^(p^k))/C_m(X^(p^(k-1)))

Now for any integer we have x^(p^k) == x^(p^(k-1)) mod p^k, so 
C_m(x^(p^k)) == C_m(x^(p^(k-1))) mod p^k.  So, unless 
C_m(x^(p^(k-1))) == 0 mod p, C_n(x) == 1 mod p^k.  This is true
for all primes dividing n.  Thus, using Chinese Remainder Theorem:

C_n(x) == 1 mod n unless there is some prime p | n such that 
C_m(x^(p^(k-1)) == 0 mod p, where n = p^k m.

Further, we know that any prime p such that C_m(X) has
a root mod p must be either a divisor of m or greater than m.

In the case m=1, i.e. n = p^k is a prime power, we have

C_n(X) = (X^(p^k)-1)/(X^(p^(k-1))-1) = sum_{j=0}^{p-1} X^(j*p^(k-1)).

Then it should be an easy exercise to prove C_n(x) == 1 mod n 
unless x == 1 mod p.

For example, for n=24 = 2^3 * 3, we look at the following cases:
 
(1) p^k=2^3, m=3: since 2 < 3, C_24(x) == 1 mod 2^3 for all x.
(2) p^k = 3, m=8: since 3 < 8, C_24(x) == 1 mod 3 for all x.
Therefore C_24(x) == 1 mod 24 for all x.

On the other hand, for n=26 = 2*13, (1) since 2 < 13, C_26(x) == 1 mod 2 
for all x. (2) 13 > 2, so C_2 might have roots mod 13. Of course it does: 
C_2(x) == 0 mod 13 if x == 12 mod 13. Thus C_26(x) == 1 mod 26 unless x == 
12 mod 13.

Cheers,
Robert

On Sep 8 2016, Peter Lawrence wrote:

> > That's a nice triangle - please go ahead and submit it. When you  
>have an
> > A-number for it,
> > you might send a follow-up message here so people can look at it.
> >
> > Best regards
> > Neil
> >
> > Neil J. A. Sloane, President, OEIS Foundation.
> > 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
> > Also Visiting Scientist, Math. Dept., Rutgers University,  
>Piscataway, NJ.
> > Phone: 732 828 6098; home page: http://NeilSloane.com
> > Email: njasloane at gmail.com
>
>Neil,
>      it is A276469, awaiting review, and I am wondering if you can
>possibly fast-track it, because
>
>it appears to define a simple function that evaluates to either 1
>or the largest prime factor of n, which to me is absolutely astounding,
>and I'd like some real Number Theorists to take a look at it.
>
>sincerely,
>Peter A. Lawrence.
>
>
>NAME
>allocated for Peter A. Lawrence
>modulo N values of N'th cyclotomic polynomial, triangle of
>
>DATA
>1, 1, 0, 1, 0, 1, 1, 2, 1, 2, 1, 0, 1, 1, 1, 1, 1, 3, 1, 1, 3, 1, 0,  
>1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1,  
>1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  
>1, 1, 1, 1, 1, 1, 1, 1, 1
>
>OFFSET
>1,8
>
>COMMENTS
>begin {
>several patterns are apparent by observation
>1) (mod p)  C_p(k) == 1, except C_p(1) = 0, for prime p, 0<=k<p.
>2) (mod 2^e) C_[2^e](k) == 1 k odd, = 0 k even, for e>1, 0<=k<2^e
>3) (mod p^e) C_[p^e](k) == 1, except C_[p^e](1+np) = p, e>1, 0<=n<p^ 
>(e-1)
>4.a) (mod m) C_m(k) for some composite m has values all 1's,
>      but it is not clear for with m this happens,
>4.b) (mod m) C_m(m) for other composite m has values 1 and x,
>4.c) with recurring period x
>4.d) x is largest prime dividing m
>(1) is trivial, I suspect (2) and (3) are simple algebra-crunching,
>(4) seems to be a genuine conjecture worth a Number Theorist's time.
>(4) seems to partition the natural numbers into
>     primes union A253235 union A276628
>} end Peter A. Lawrence
>
>FORMULA
>a(i,j) = Cyclotomic_i(j) (mod i);  i=1,...;  j=0,...,i-1
>
>EXAMPLE
>let C_N(x) be the N'th cyclotomic polynomial, then the
>values of C_N(k) mod N, m=0,...,N-1, are
>     \  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 -- k -->
>C_1:  1
>C_2:  1 0
>C_3:  1 0 1
>C_4:  1 2 1 2
>C_5:  1 0 1 1 1
>C_6:  1 1 3 1 1 3      (note period 3)
>C_7:  1 0 1 1 1 1 1
>C_8:  1 2 1 2 1 2 1 2
>C_9:  1 3 1 1 3 1 1 3 1     (note period 3)
>C_10:  1 1 1 1 5 1 1 1 1 5      (note period 5)
>C_11:  1 0 1 1 1 1 1 1 1 1 1
>C_12:  1 1 1 1 1 1 1 1 1 1 1 1
>C_13:  1 0 1 1 1 1 1 1 1 1 1 1 1
>C_14:  1 1 1 1 1 1 7 1 1 1 1 1 1 7     (note period 7)
>C_15:  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
>C_16:  1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
>
>CROSSREFS
>A253235: numbers n such that this seq A276469(n,j) are all 1's
>A276628: numbers n such that this seq A267469(n,j) are not all 1's
>
>KEYWORD
>allocated
>nonn,changed
>
>AUTHOR
>Peter A. Lawrence, Sep 04 2016
>
>STATUS
>approved
>editing
>
>--
>Seqfan Mailing list - http://list.seqfan.eu/
>
>