Small prime factors of large integers: A closer look.

Expand Messages
• 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
Message 1 of 4 , Jul 4, 2009
• 0 Attachment
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.
• ... You proof is also good for composite p, provided that p q ? In that case iteration of
Message 2 of 4 , Jul 4, 2009
• 0 Attachment
Kermit Rose <kermit@...> wrote:

> 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))

You proof is also good for composite p, provided that
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 +
Message 3 of 4 , Jul 4, 2009
• 0 Attachment
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]
• ... Aloha ! 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
Message 4 of 4 , Jul 5, 2009
• 0 Attachment
>
> 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

Aloha !

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
Your message has been successfully submitted and would be delivered to recipients shortly.