Least Prime Factor Sequences - Updated

GROUPS OF LINEAR FUNCTIONS ON Zp AND THE LEAST PRIME FACTOR SEQUENCES Tue Ngoc Ly University of South Florida [email protected] January 6th , 2009 Abstract There are many problems of linear functions on finite rings. Among those are some iteration problems that are simply stated but extremely hard to show, such as the 3x + 1 conjecture, or the greatest prime factor conjecture, that dealing with divisibility and periodicity of linear functions. In this paper, I will prove a part of similar conjecture about the periodicity of the linear least prime factor sequences, using groups of linear functions on Zp

1

Introduction

A linear greatest prime factor (gpf ) sequence is defined as xn+1 = gpf (axn + b) for some positive integers a, b, and x0 with gpf (x) be the greatest prime factor of x. The gpf conjecture states that for any positive integers a, b, and x0 , the corresponding linear gpf sequence always ends up in a loop (ultimately periodic). One of the consequence of this conjecture is the famous 3x + 1 conjecture, which still remains unsolved. The other interesting consequence is the infiniteness of Mersene’s Primes. Some very limited cases has been proved for the gpf conjecture (see [1]), but the complete proof for this conjecture is still unknown. Let’s consider a weaker version of the gpf conjecture: the linear least prime factor (lpf ) sequence. Since lpf (x) ≤ gpf (x) for any integer x, if we believe in the ultimate periodicity of the linear gpf sequences, then so are the linear lpf sequences.

1

2

Simple cases

Let φa,b (x) = ax + b. Most of the results obtained in this paper are relied on the following lemma Lemma 1 Let a and b be two integers. If there exist two positive integers n and m such that for any integer x0 , m | φia,b (x0 ) for some 1 ≤ i ≤ n, then the lpf sequences of a and b are ultimately periodic for any x0 . √ Proof: Notice that if x is composite then lpf (x) ≤ x. Let M = max{x0 k(x) , an+1 , b}. Let k(x) be the smallest positive integer such that φa,b (x) is composite. Clearly that k(x) ≤ n for any x. If x ≤ M then we will have that: v u q q n q u X k(x) k(x) k(x) n ai ≤ M lpf (φa,b (x)) ≤ φa,b (x) ≤ φa,b (M ) ≤ φa,b (M ) ≤ tM i=0

Therefore, xi ≤ φna,b (M ) for any i. Thus the sequence is bounded and hence ultimately periodic  Proposition 1 If gcd(a, b) > 1 or a = 1 then the linear lpf sequence is ultimately periodic. Proof. Clearly that if gcd(a, b) > 1 then lpf (ax + b) <= gcd(a, b), so xn ≤ gcd(a, b) for n ≥ 1. Hence the linear lpf sequence is ultimately periodic. Let p be the smallest prime that does not divide b. Then clearly let n = p and m = p are two numbers that satisfy the conditions in Lemma 1. That proves the case when a = 1  For the similar results for linear gpf sequences, see [1].

3

Groups of Linear Functions on Zp

Given a linear lpf sequence xn+1 = lpf (axn + b) . So xn+1 is the least prime p such that axn + b ≡ 0 (mod p). Consider the collection of linear functions ϕa,b on Zp with ϕa,b (x) = ax + b, p - a. We have the following lemma Lemma 2 The collection of linear functions ϕa,b on Zp with ϕa,b (x) = ax + b, p - a forms a group under composition operation, called AGL(p). Furthermore, AGL(p) ∼ = Up o Zp

2

Given ϕa,b ∈ AGL(p), ϕna,b (x) = an x + b

n−1 X

ai

i=0

Let d = |ϕa,b | be the order of ϕa,b in AGL(p). Then we have that ad ≡ 1 Pd−1 (mod p) and b ≡ 0 (mod p) or i=0 ai ≡ 0 (mod p). m(x)

Let m(x) be the least positive integer such that ϕa,b (x) ≡ x (mod p). Since ϕda,b (x) ≡ x (mod p), we must have m(x) | d. Consider the order of AGL(p): |AGL(p)| = |Up o Zp | = |Up | · |Zp | = p(p − 1) So there exists a cyclic subgroup of AGL(p) of order p. |ϕa,b | = p, then we must have ap ≡ 1 (mod p)

Assume that

Recall the Fermat’s Little Theorem that ap−1 ≡ 1 (mod p) for any prime p Pp−1 and p - a, that implies a ≡ 1 (mod p), i=0 ai ≡ 0 (mod p) and p - b. The converse is quite obvious. Lemma 3 |ϕa,b | = p if and only if a ≡ 1 (mod p) and p - b.

4

Main results

Proposition 2 If a, b are two integers such that gcd(a, b) = 1 and there exists a prime p satisfying p | a − 1 and p - b then for any integer x, there exists a positive integer n ≤ p such that p | φna,b (x). Proof. From the previous section, we have that |φa,b | = p. Since m(x) | |φa,b | and p - b, m(x) = p. So, {φia,b (x) mod p | i ∈ N} = p. Therefore, there exists a positive integer n ≤ m(x) = p such that φna,b (x) ≡ 0 (mod p)  Theorem 1 If a and b are two integers satisfying the conditions in Proposition 2, then for any x0 , the corresponding linear lpf sequence is ultimately periodic. Proof. Let p be the smallest prime such that p | a − 1 and p - b. Then the theorem followed directly by Proposition 2 and Lemma 1 

3

5

Open problems

There’s still the second case when any prime factor p of a − 1 divides b. If it is proved then so is the lpf conjecture. And also the problems of linear gpf sequences still remain. Conjecture 1 Every linear lpf sequence is ultimately periodic. Conjecture 2 Every linear gpf sequence is ultimately periodic.

References [1] Caragiu, M. and Scheckelhoff, L., The Greatest Prime Factor and Related Sequences, JP J. of Algebra, Number Theory and Appl. 6 (2006) , 403 - 409. [2] Hungerford, T., Algebra, Graduate Texts in Mathematics, Springer (1974).

4