wu :: forums « wu :: forums - Constant Modulo N » Welcome, Guest. Please Login or Register. Aug 8th, 2022, 4:21pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    putnam exam (pure math) (Moderators: Eigenray, towr, SMQ, william wu, Grimbal, Icarus)    Constant Modulo N « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Constant Modulo N  (Read 1144 times)
william wu

Gender:
Posts: 1291
 Constant Modulo N   « on: Aug 23rd, 2003, 9:55pm » Quote Modify

For any positive integer n, show that the sequence { 2 , 22 , 22[sup2] , ... } eventually becomes a constant modulo n.
 « Last Edit: Aug 23rd, 2003, 9:57pm by william wu » IP Logged

[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
Sir Col
Uberpuzzler

impudens simia et macrologus profundus fabulae

Gender:
Posts: 1825
 Re: Constant Modulo N   « Reply #1 on: Aug 24th, 2003, 7:18am » Quote Modify

I don't think this works in general?!

Let uk represent the kth term of the sequence.

Let us assume that uk [equiv] b mod n for some k.
uk+1 = (uk)2 [equiv] b2 mod n.

Now consider n=7.
u1 = 2 [equiv] 2 mod 7.
u2 [equiv] 4 mod 7
u3 [equiv] 2 mod 7, and so on.

That is, it will alternate congruence with 2 and 4, never becoming constant.

The only way to guarantee this to work, is for b=0 or b=1 for some k. In other words, n=uk or n=uk–1.

For example, the actual sequence (when evaluated) is: 2,4,16,256,65536.

2 [equiv] 2 mod 15
4 [equiv] 4 mod 15
16 [equiv] 1 mod 15
256 [equiv] 1 mod 15, and so on.

Have I missed something?
 IP Logged

mathschallenge.net / projecteuler.net
hv2004
Guest

 Re: Constant Modulo N   « Reply #2 on: Aug 24th, 2003, 7:53am » Quote Modify Remove

This is USAMO 1991/3. The solution involves mathematics induction and Fermat-Euler theorem. An alternate and more difficult version of this problem is Putnam 1997/B5. This problem is also similar to Putnam 1985/A4.
 IP Logged
Sir Col
Uberpuzzler

impudens simia et macrologus profundus fabulae

Gender:
Posts: 1825
 Re: Constant Modulo N   « Reply #3 on: Aug 24th, 2003, 8:10am » Quote Modify

But doesn't uk mod 7, alternate?
 IP Logged

mathschallenge.net / projecteuler.net
wowbagger
Uberpuzzler

Gender:
Posts: 727
 Re: Constant Modulo N   « Reply #4 on: Aug 24th, 2003, 8:42am » Quote Modify

on Aug 24th, 2003, 7:18am, Sir Col wrote:
 Let uk represent the kth term of the sequence.   Let us assume that uk [equiv] b mod n for some k. uk+1 = (uk)2 [equiv] b2 mod n.

I don't think that's true, because  uk+1 = 2uk.

So u4 = 65536, u4 = 2 (mod 7).

Don't know whether this helps much in finding the constant n.

Or am I the one who's wrong?
 « Last Edit: Aug 24th, 2003, 8:50am by wowbagger » IP Logged

Sir Col
Uberpuzzler

impudens simia et macrologus profundus fabulae

Gender:
Posts: 1825
 Re: Constant Modulo N   « Reply #5 on: Aug 24th, 2003, 8:54am » Quote Modify

Ah, it looked to me as if each new term was being squared. It is not clear from the question if uk+1=uk2 or uk+1=2uk and that would make a difference.

As it is taken from a genuine paper, it must have a solution. You must be right, wowbagger. Cheers!

Hmm. Back to pencil and paper...
 « Last Edit: Aug 24th, 2003, 9:01am by Sir Col » IP Logged

mathschallenge.net / projecteuler.net
DH
Guest

 Re: Constant Modulo N   « Reply #6 on: Aug 29th, 2003, 12:21pm » Quote Modify Remove

Suppose this holds true for all numbers smaller than n.
The sequence 21 mod n , 22 mod n , 23 mod n ... either converges to 0 or it is periodic and the period is T < n.The period cannot be n because all numbers including 0 would have to be part of the sequence.

u(k) = 2u(k-1)
u(k) mod n = 2u(k-1) mod n = 2( u(k-1) mod T ) mod n

Because T<n we already know that u(k-1) mod T will eventually converge. So u(k) will eventually converge.

To complete the induction it's easy to verify that the property holds true for n=1.
 IP Logged
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »