wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Extending Euler's Theorem
        
(Message started by: SMQ on Oct 10^th, 2007, 10:53am)

Title: Extending Euler's Theorem
Post by SMQ on Oct 10^th, 2007, 10:53am

Not so much a puzzle as a question, I guess:

After my stumbling in this thread (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1191621278) I've done a bit more experimenting and feel reasonably confident in the following two claims:

1) For all a http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif, m http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbn.gif there exists some least nonnegative t http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif such that ahttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supvarphi.gif^{(m) + t} http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif a^t (mod m), where http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif(m) is Euler's Totient Function (http://en.wikipedia.org/wiki/Euler%27s_totient_function).

2) If and only if GCD(a, m) = 1 then t = 0 (Euler's Theorem (http://en.wikipedia.org/wiki/Euler's_theorem)); otherwise t = max(_{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lceil.gif}M_i/A_i_{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rceil.gif}), where for prime factors p₁, p₂, ..., p_n common to a and m, M_i is the multiplicity of p_i in m and A_i is the multiplicity of p_i in a.

I have empirical evidence that no violation of those claims exists for 1 _{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif} m _{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif} ~~2,500~~ ~~25,000~~ ~~80,000~~ 250,000, and an intuitive feel for why they should be true, but no proof of either claim; nor have I been able to find a reference one way or the other. I'm wondering a) if this is a (well) known (or trivial) result that I'm just unable to find, and b) if anyone here has a proof (or, more interesting, a disproof).

--SMQ

Title: Re: Extending Euler's Theorem
Post by Barukh on Oct 15^th, 2007, 9:02am

Interesting. I think your conjectures are true. Here is an analysis of an important special case which may be hopefully converted to a full proof.

Let gcd(a, m) be a power of a prime p. That is, a = rpⁱ, m = sp^j, r, s, p are relatively prime. Let further d = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif(s). Then, (rpⁱ)^d+1 = rpⁱ mod s. That is, (rpⁱ)^d+1 - rpⁱ = qs. Since p doesn’t divide s, it follows pⁱ | q, and thus (rpⁱ)^d+1 = rpⁱ mod spⁱ.

Note also that pⁱ⁺¹ doesn’t divide q (otherwise p divides r, which is impossible). If j http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif i, we are done. Otherwise, (rpⁱ)^u(rpⁱ)^d+1 = rp^u+1 mod sp^j, where u is the least integer such that ui http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif j – i. But this is exactly the condition stated by SMQ in the second claim.

Finally, because d | http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif(a), the first statement also follows.

Title: Re: Extending Euler's Theorem
Post by Pietro K.C. on Oct 17^th, 2007, 12:21am

That is an extremely interesting question.

Given a finite set S with a binary operation * defined on it, the "powers" of any given element s in S, ie

s, s², s³, ...

must eventually repeat some value. If s^k is the first such repeated value, and s^k+T the second occurrence, then the powers go around in a circle of size T thereafter:

s^k <-- ... <-- s³ <-- s² <-- s
/ \
\ _ /

SMQ's question may thus be read as follows: is http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif(m) big enough to get out of the linear part above, and reach the loop? (If a power is in the loop, then there trivially exists your least t, since the natural numbers are well-ordered.) The answer is yes.

Let m=p^r, and a=p^sb, with p a prime number and b coprime with p. It is trivial to check that, for integer k,

s>0 and k > r/s ---> a^k=0 (mod m);

Also, for s>0,

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif(m) = p^r-1(p-1) >= 2^r-1 >= r >= r/s.

This means that, unless p does not divide a, the "going to zero" tendency outruns the "repeat in a cycle" tendency: the only repeated value is 0.

Now all we need is Chinese Remainder to glue the local results together. Break down a given m into its prime power factors, recall that http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gifis multiplicative across relatively prime numbers, and reason as follows. For each factor p^r of m, either

(i) p divides a, and, as we saw, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif(p^r) is a big enough power to reach 0 in the (mod p^r)-loop, whence a^{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif(m)} = 0 (mod p^r);

(ii) p does not divide a, and the latter is therefore already in the loop of its generated subgroup in the multiplicative group of integers prime to p^r.

Therefore, a^{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif(m)} is in the (mod m)-loop of powers of a. As regards a specific value for t=T, it is easy from the above to see what is "really" going on: modulo primes in m not dividing a, the equation

a^{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif(m)+t} = a^t

is true for every t; what is needed is some t high enough that a^t will be zero modulo those other primes. SMQ's formula is thus correct.

Title: Re: Extending Euler's Theorem
Post by cuckoo on Nov 7^th, 2007, 1:27am

Here is my proof:

let m = (p_1^M_1)*...*(p_s^M_s), then a^(\phi(m)+t)=a^t (mod m) is equivalent to

a^t * [a^\phi(m)-1] = 0 (mod p_i^M_i), for any 1<= i <=s.

if (p_i, a)=1, since \phi(m) is a multiple of \phi(p_i^M_i), so [a^\phi(m) -1] = 0 (mod p_i^M_i)
and the above equation holds forever;

if (p_i, a)>1, say the power index of p_i in a is A_i,
then we must have a^t = 0 (mod p_i^M_i). so we get : t*A_i >= M_i.

To conclude, we must have t >= max( ceil(M_i/A_i) ).

done.