EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 13, No. 1, 2020, 108-112 ISSN 1307-5543 – www.ejpam.com Published by New York Business Global Proof of Golomb’s conjecture in Fq with Γ$-pseudorandom sequences Yonghong Liu School of Automation, Wuhan University of Technology, 205 Luoshi Road, Wuhan, China Abstract. This article offers a short proof of Golomb’s conjecture, and then our results show that the sequences are pseudorandom in F2. 2020 Mathematics Subject Classifications: 11A41, 11A07, 12E20, 11B50 Key Words and Phrases: Primes, Primitive roots, Finite fields, Sequences, Golomb’s conjecture 1. Introduction Question 10208b (1992) of the American Mathematical Monthly asked: does there exist an increasing sequence {ak} of positive integers and a constant B > 0 having the property that {ak + n} contains no more than B primes for every integer n? If it turns out that a positive answer to this question became known as Golomb’s conjecture [1]. Let Fq denote the finite field of order q, where q = pn, and p is a prime, if n=1, Golomb’s conjecture equivalent to: Conjecture 1. Let α and β be two primitive roots of f(x)(mod p) in Fq, then f(α) + f(β) ≡ 1 (mod p). (1) Moreno and Sotero [2] proved that Golombs conjecture is true for all q < 260. Golomb [3] pointed out that the conjecture associated with sequences and prime numbers. Elsholtz [4] proved in 2017 that Golomb’s conjecture was false. Elsholtz gave an example to explain the Fermat numbers contains at least B + 1 primes, but his research has shown that we cannot conclude that there is any fixed n such that the sequence {22i +n} contains innitely many primes. Certainly! the conjecture is true for the special case. Because of pseudorandom sequences unique characteristic they have been widely used in many fields. In this paper we prove that the Golombs conjecture in Fq, and we show that a new pseudorandom sequence (denote Γ$) in F2 is existent by Golomb conjecture and additive groups. DOI: https://doi.org/10.29020/nybg.ejpam.v13i1.3594 Email address: hylinin@whut.edu.cn (Y. Liu) http://www.ejpam.com 108 c© 2020 EJPAM All rights reserved. Y. Liu / Eur. J. Pure Appl. Math, 13 (1) (2020), 108-112 109 2. Proof of the Golomb conjecture Theorem 1. If $∑ n=1 (−1)n+12$−n = p, (2) is prime, then $ is prime. Proof. If $ = 1, then p is not prime. Let $ be composite and let m be divisor. Since $ = km satisfies 1 < k < $, and that k∑ n=1 (−1)n+12k−n ∣∣∣∣∣ $∑ n=1 (−1)n+12$−n. (3) We have 1 < k∑ n=1 (−1)n+12k−n < $∑ n=1 (−1)n+12$−n, (4) and so p is not prime, a contradiction. For our next discussion, Γ$ numbers are defined by Γ$ = $∑ n=1 (−1)n+12$−n, (5) so that  Γ3 = 3, Γ5 = 11, Γ7 = 43, Γ11 = 683, Γ13 = 2731, Γ17 = 43691, Γ19 = 174763, Γ23 = 2796203. (6) As an application of the Γ$ numbers, we give the following theorem. Theorem 2. 3 is a primitive root of Γ7 (or Γ11). Theorem 3. Golomb’s conjecture (Conjecture 1) on FΓ17, which is true. Proof. We can now find tow primitive roots of f(x). By Theorem 1. Since Γ17 prime is 43691, and we have f(α) = 3$−2 and f(β) = 2 · 3$−2. (7) Y. Liu / Eur. J. Pure Appl. Math, 13 (1) (2020), 108-112 110 It follows that f(α) = 315 (mod 43691) and f(β) = 2 · 315 (mod 43691). (8) The same result is primitive root of modulus 34961. Hence 315 + 2 · 315 = 316 ≡ (−1)16 ≡ 1 (mod 43691), (9) as desired. Theorem 4. Golomb’s conjecture (Conjecture 1) on FΓ7 (or FΓ11), which is true. Combining the Theorem 2.3 and Theorem 2.4, we obtain the following corollary. Corollary 1. If Γ$ is prime and f(α) = 3$−2, f(β) = 2 · 3$−2 (10) is primitive root of f(x)(mod Γ$), then f(α) + f(β) ≡ 1 (mod Γ$). (11) 3. Γ$-pseudorandom sequences Definition 1. Let $ is prime and let µ is primitive root of modulus Γ$ such that Eq. (5). We say that Γ$ is a period of pseudorandom sequence if X = [a0 a1 a2 · · · ap−2 ap−1] (ai ∈ Fq) (12) with the following properties: a0 = +1. (13) ai = (−1)t = { +1 if t is even −1 if t is odd, (14) for i ≡ µt (mod Γ$), (15) where 1 < i < p−1. Definition 2. Let η be an additive group of F2 (for +1 and −1). Then multiplicative group is isomorphic which constitutes by these two integers, and we have η(0) = 1, η(1) = −1. (16) Our new result is the following theorem. Y. Liu / Eur. J. Pure Appl. Math, 13 (1) (2020), 108-112 111 Theorem 5. Suppose that the pseudorandom periodic sequence Γ$ acts transitively on the F2. Then Cx(j) = { Γ$ if j ≡ 0 (mod Γ$) −1 if j 6≡ 0 (mod Γ$). (17) Proof. By Definition 1. First, we have Cx(0) = Γ$. (18) Let j 6≡ 0 (mod Γ$). We define X by X = (x0, x1, · · · ). (19) Next let f(y) be a minimal polynomial of X with X∈ G(f). Now If f(x) is nth order primitive polynomial f(y) = cny n + cn−1y n−1 + · · ·+ c1y + c0 (c0cn 6= 0). (20) Then X satisfies the homogeneous linear difference equation of nth order n∑ i=0 cixk−i = 0 (k ≥ n). (21) We have c0 = 1 = cn. (22) To find that the linear recursive relation for Eq.(21) so that X moves that S steps to the left, we have T s(X) = (xs, xs+1, xs+2, · · · ) ∈ G(f), (23) and X + T s(X) = (x0 + xs, x1 + xs+1, x2 + xs+2, · · · ) ∈ G(f). (24) If s 6≡ 0 (mod Γ$), (25) since period X is Γ$, then X + T s(X) 6= 0. (26) But nonzero sequence is Γ$ in G(f), so 1 there are $∑ n=1 (−1)n+12$−n−1 REFERENCES 112 times in a period in X + T s(X) and 0 there are $∑ n=1 (−1)n+12$−n−1 − 1 times in a period in X + T s(X). Finally, by Definition 2, we have Cx(j) = cx(0)∑ i=0 η(xi)η(xi+s) = cx(0)∑ i=0 η(xi + xi+s) = $∑ n=1 (−1)n+12$−n−1 · (−1) + ( $∑ n=1 (−1)n+12$−n−1 − 1 ) · 1 = −1, (27) as desired. References [1] S. W. Golomb, Infinite sequences with finite cross-correlation, In SETA (2010), LNCS, Springer, Berlin, 6338(2010), 430-441. [2] O. Moreno & J. Sotero, Computational approach to conjecture A of Golomb, Con- gressus Numerantium, 70(1990), 7-16. [3] S. W. Golomb, “Conjectures involving sequences and prime numbers. Sequences and their applications”, In SETA (2014), LNCS, Springer, Cham, Switzerland, 8865(2014), 263-266. [4] C. Elsholtz, Golombs conjecture on prime gaps, Amer. Math. Monthly, 124(2017), 365-368. https//doi:10.4169/amer.math.monthly.124.4.365