proposed

approved

editing

proposed

Conjecture 2: for a prime p >= 3, gcd(x^(Zs(d,p,1))-1, (x+1)^(Zs(d,p,1))-1) != 1 if and only if d is an odd prime power > 1. other than (d,p) = (7,3), (7,9), (13,3), (37,3), (43,3), (79,3).

Jianing Song: Among odd numbers <= 89: a proper divisor of Zs(d,2,1) is also a term for d = 23, 29, 37, 39, 41, 43, 47, 51, 53, 59, 67 (761838257287 checked in 4h44min), 71, 73, 79, 81 (2593*97685839 in 2h6min), 83, 87 (9857737155463 checked in 13h39min).

Jianing Song: After 50 hours of searching, I am forced to say that didn't find a solution to x^(Zs(d,p,1)) = (x+1)^(Zs(d,p,1)) = 1 in F_{p^d} for (p,d) = (2,155), (7,27), (13,27), (7,81)

In particular, let p and r be distinct primes, r >= 5, t >= 1. SetLet m = 1 + Zs(d,p^(r^(t-,1)) + p^(2*r^(t) is the d-1)) + ... + th Zsigmondy number with parameters (p^((r-1)*r^(t-,1)), ), then gcd(x^(Zs(r^m-t,p,1))-1, (x+1)^(Zs(r^t,p,1)^m-))-1) != 1 in F_p[x]. This is because for d != 2, Zs(d,p,1) = Phi_d(p)/r if d is of the form r^{t'}*ord(p,r) and Phi_d(p) otherwise (see A323748), where ord(a,k) is the multiplicative order of a modulo k, Phi_d(x]: in) is thisthe cased-th wecyclotomic havepolynomial. Here qd = p^(r^t), , so Zs(d,p,1) = Phi_d(p)/r if p == 1 (mod r), Phi_d(p) otherwise. Note that m > Phi_{r^t}(p) = 1 + p^(r^(t-1)) + p^(2*r^(t-1)) + ... + p^((r-1)*r^(t-1)) > q^(3/4) = p^(3/4*r^t) since r >= 5. It is easy to show that Zs(p^r,p,1) <= q^(3/4) can only happen with r = 5, p == 1 (mod 5) and p <= 601, then we can check that gcd(x^(Zs(r^t,p,1))-1, (x+1)^(Zs(r^t,p,1))-1) = gcd(x^((p^4+p^3+p^2+p+1)/5)-1, (x+1)^((p^4+p^3+p^2+p+1)/5)-1) != 1 in F_p[x] in this case.

Conjecture: Let Zs(d,2,1) is the d-th Zsigmondy number with parameters (2,1) (A064078), then Zs(d,2,1) is a term if and only if d is odd and d != 1, 15, 21. Verified for odd numbers up to 91. Note that the comment above shows that this is true for powers > 1 of a prime r >= 5, because in this case we have Zs(r^t,2,1) = Phi_{r^t}(2) = 1 + 2^(r^(t-1)) + 2^(2*r^(t-1)) + ... + 2^((r-1)*r^(t-1)), where Phi_d(x) is the d-th cyclotomic polynomial: if Zs(r^t,2,1) != Phi_{r^t}(2), then Phi_{r^t}(2) is disivisible by r, so the prime power r^t must be of the form r^{t'}*ord(2,r) for some t', where ord(a,k) is the multiplicative order of a modulo k. This implies that ord(2,r) = 1, which is impossible. (End)

Conjecture 1: Zs(d,2,1) is a term if and only if d is odd and d != 1, 15, 21. Verified for odd numbers up to 91.

Conjecture 2: for a prime p >= 3, gcd(x^(Zs(d,p,1))-1, (x+1)^(Zs(d,p,1))-1) != 1 if and only if d is an odd prime power > 1.

Note that the comment above shows that both conjectures are true for powers > 1 of a prime r >= 5. (End)

In particular, let p and r be distinct primes, r >= 5, t >= 01. Set m = 1 + p^(r^^(t) + -1)) + p^(2*r^^(t) + ... + -1)) + ... + p^((r-1)*r^^(t), -1)), then gcd(x^m-1, (x+1)^m-1) != 1 in F_p[x]: in this case we have q = p^(r^(^t+1)), ), so m > p^((r-1)*r^^(t) > -1)) > q^(3/4) since r >= 5.

Conjecture: Let Zs(d,2,1) is the d-th Zsigmondy number with parameters (2,1) (A064078), then Zs(d,2,1) is a term if and only if d is odd and d != 1, 15, 21. Verified for odd numbers up to 91. Note that the comment above shows that this is true for powers > 1 of a prime r >= 5, because in this case we have Zs(r^t,2,1) = Phi_{r^t}(2) = 1 + 2^(r^(t-1)) + 2^(2*r^(t-1)) + ... + 2^((r-1)*r^(t-1)), where Phi_d(x) is the d-th cyclotomic polynomial: if Zs(r^t,2,1) != Phi_{r^t}(2), then Phi_{r^t}(2) is disivisible by r, so the prime power r^t must be of the form r^{t'}*ord(2,r) for some t', where ord(a,k) is the multiplicative order of a modulo k. This implies that ord(2,r) = 1, which is impossible. (End)

proposed

editing

editing

proposed

Propostion. LetIn general, let p be a prime, gcd(m,p) = 1. Let , q > 1 be the smallesta power of p that is congruent to 1 modulo m. ThenIn the finite field F_q, the roots to x^m-1 are the nonzero ((q-1)/m)-th powers, so gcd(x^m-1, (x+1)^m-1) != 1 if and only if there are two nonzero ((q-1)/m)-th powers in F_p[x] ifq that differ by 1. If we homogenize, this is equivalent to x^((q-1)/m) + y^((q-1)/m) = z^((q-1)/m > ) having solutions in (F_q^(3/4)* (dehomogenize by setting y = 1).

Proof. InLet p be thea finiteprime, gcd(m,p) = 1. Suppose fieldthat F_q, > 1 is the smallest power of p that is rootscongruent to x^m-1 are themodulo nonzero ((q-1)/m)-th powers, sothen gcd(x^m-1, (x+1)^m-1) != 1 if and only if there are two nonzero ((q-1)/m)-th powers in F_q that differ by 1. If we homogenize, this is equivalent to p[x^((q-1)/m) + y^((q-1)/m) = z^((q-1)/m) having solutions] if in (F_m > q)* (dehomogenize by setting y = 1). Set^(3/4): set k = (q-1)/m and A_1, A_2 both be the set of nonzero ((q-1)/m)-th powers in F_q (so |A_1| = |A_2| = m). Let N be the number of solutions to x^((q-1)/m) + y^((q-1)/m) = z^((q-1)/m) has solutions in (F_q)*, then by Theorem 7.1 of the László Babai link, we have N > m^2*(q-1)/q - (q-1)*sqrt(q) >= 0.

Corollary. LetIn particular, let p and r be distinct primes, r >= 5, t >= 0. Set m = 1 + p^(r^t) + p^(2*r^t) + ... + p^((r-1)*r^t), then gcd(x^m-1, (x+1)^m-1) != 1 in F_p[x].]: in this case we have q = p^(r^(t+1)), so m > p^((r-1)*r^t) > q^(3/4) since r >= 5.

Proof. In this case we have q = p^(r^(t+1)), so m > p^((r-1)*r^t) > q^(3/4) since r >= 5.

(PARI) isA261524(n, p=2) = my(d=znorder(Mod(p, n)), c=ffgen(p^d, 'c), g=ffprimroot(c)); forstep(e=0, p^d-2, (p^d-1)/n, if((g^e+1)^n==1, return(1))); return(0) \\ Jianing Song, Oct 14 2023, based on the equivalence of gcd(x^m-1, (x+1)^m-1) != 1 and two ((q-1)/m)-th powers in F_q differing by 1 (see Comments)

approved

editing

Jianing Song: Added my program.

reviewed

approved

proposed

reviewed

editing

proposed