- Small prime factors of large integers: A closer look.

137**(137**(137**137) mod 29

EulerPhi(29)=28

137**(137**137) mod 28

EulerPhi(28) = 12

137**137 mod 12

EulerPhi(12) = 4

137 = 1 mod 4

137**137 mod 12 = 137 ** 1 mod 12 = 137 mod 12 = 5 mod 12

137**(137**137) mod 28 = 137**5 mod 28 = 9

137**(137**(137**137) mod 29 = 137 ** 9 mod 29

= 21**9 mod 29 = 14

73 mod 29 = 15

137**(137**(137**137) + 73 = 0 mod 29

Theorem:

If q is an odd positive prime and p is a positive prime

with p < q.

Then there exist an integer k such that

q***k mod p = q***(k+1) mod p.

Note: q***k is defined recursively as follows.

q***0 = 1

q***1 = q

q***2 = q**q

q***m = q**(q***(m-1))

Proof.

Consider the sequence

EulerPhi(p)

EulerPHi( EulerPHi(p))

EulerPHi( EulerPHi( EulerPhi(p)))

etc

For ease of reference, define recursively,

EulerPhi**1 (p) = EulerPhi(p)

EulerPHi**m (p) = EulerPhi( EulerPHi**(m-1) (p) )

The sequence

EulerPHi**j (p), for j = 1,2,3,...

is a decreasing sequence, which eventually

reaches a value

EulerPhi**k (p) with the property that

q mod EulerPhi**k(p) = 1

Note: In the extreme case, EulerPhi**k(p) will equal 2.

Then if we evaluate q***(k+1) mod p, we observe that

q**q = 1 mod EulerPHi**k (p)

and hence

q***(k+1) = q***k mod p. - --- In primenumbers@yahoogroups.com,

Kermit Rose <kermit@...> wrote:

> If q is an odd positive prime and p is a positive prime

You proof is also good for composite p, provided that

> with p < q.

> Then there exist an integer k such that

> q***k mod p = q***(k+1) mod p.

> Note: q***k is defined recursively as follows.

> q***0 = 1

> q***1 = q

> q***2 = q**q

> q***m = q**(q***(m-1))

p < q and q is prime, as you were careful to stipulate.

But what if p > q ?

In that case iteration of eulerphi on p may

yield a value that is not coprime to q, so

you may not rely on the Euler-Fermat theorem.

The same problem may occur with p < q, if q is not prime.

David - In other words if

a^b^d...^x + c = f(x) (where ab,c...x belong to N, x is the only

variable)

Then a ^b^d...^(x + k*eulerphi(eulerphi(eulerphi...(f(x))))) + c is

congruent to 0 (mod(f(x) .(k also belongs to N).

Hope to publish proof of the above, based on my published paper "Euler's

generalisation of Fermat's theorem - a further generalisation" in the

near future.

Devaraj

On Sat, Jul 4, 2009 at 7:21 PM, Kermit Rose <kermit@...> wrote:

>

>

>

>

> Small prime factors of large integers: A closer look.

>

> 137**(137**(137**137) mod 29

>

> EulerPhi(29)=28

>

> 137**(137**137) mod 28

>

> EulerPhi(28) = 12

>

> 137**137 mod 12

>

> EulerPhi(12) = 4

>

> 137 = 1 mod 4

>

> 137**137 mod 12 = 137 ** 1 mod 12 = 137 mod 12 = 5 mod 12

>

> 137**(137**137) mod 28 = 137**5 mod 28 = 9

>

> 137**(137**(137**137) mod 29 = 137 ** 9 mod 29

>

> = 21**9 mod 29 = 14

>

> 73 mod 29 = 15

>

> 137**(137**(137**137) + 73 = 0 mod 29

>

> Theorem:

>

> If q is an odd positive prime and p is a positive prime

> with p < q.

>

> Then there exist an integer k such that

>

> q***k mod p = q***(k+1) mod p.

>

> Note: q***k is defined recursively as follows.

>

> q***0 = 1

> q***1 = q

> q***2 = q**q

> q***m = q**(q***(m-1))

>

> Proof.

>

> Consider the sequence

>

> EulerPhi(p)

> EulerPHi( EulerPHi(p))

> EulerPHi( EulerPHi( EulerPhi(p)))

> etc

>

> For ease of reference, define recursively,

>

> EulerPhi**1 (p) = EulerPhi(p)

> EulerPHi**m (p) = EulerPhi( EulerPHi**(m-1) (p) )

>

> The sequence

>

> EulerPHi**j (p), for j = 1,2,3,...

>

> is a decreasing sequence, which eventually

>

> reaches a value

>

> EulerPhi**k (p) with the property that

>

> q mod EulerPhi**k(p) = 1

>

> Note: In the extreme case, EulerPhi**k(p) will equal 2.

>

> Then if we evaluate q***(k+1) mod p, we observe that

>

> q**q = 1 mod EulerPHi**k (p)

>

> and hence

>

> q***(k+1) = q***k mod p.

>

>

>

[Non-text portions of this message have been removed] - --- In primenumbers@yahoogroups.com, Devaraj Kandadai typed:
>

Aloha !

> In other words if

> a^b^d...^x + c = f(x) (where ab,c...x belong to N, x is the only variable)

>

> Then a ^b^d...^(x + k*eulerphi(eulerphi(eulerphi...(f(x))))) + c is

> congruent to 0 (mod(f(x) .(k also belongs to N).

>

> Hope to publish proof of the above, based on my published paper "Euler's

> generalisation of Fermat's theorem - a further generalisation" in the

Before publishing the proof, consider

f(x) = a^x + c = 2^2 + 4 = 8

eulerphi(8) = 4

2^(2+k*4) + 4 = 4 (mod 8) for all k > 0.

Maximilian