My Math Forum  

Go Back   My Math Forum > Math Forums > Math Events

Math Events Math Events, Competitions, Meetups - Local, Regional, State, National, International

LinkBack Thread Tools Display Modes
December 26th, 2006, 08:27 AM   #1
Joined: Nov 2006

Posts: 20
Thanks: 0

1991 usa math olympiad question!

Show that for any fixed integer n >=1, the sequence:
2, 2^2, 2^(2^2), 2^(2^(2^2))... mod n $$
is eventually constant. [That is, the sequence is defined:
a_1=2, ai+1 = 2a_i. and you need to show that, for
any positive integer n, the sequence a_1 mod n, a_2 mod n,
.... is eventually constant.]

Hints: Certainly the Euler-Fermat Theorem
is involved in some way, but be careful! Just because ab mod n$
doesn't mean 2a 2b mod n. What must be true of a and b
in order for 2a to be congruent to 2b mod n?

It might be enough to prove the result when n is prime, but that
might not be relevant. You might consider using induction or its
cousin, infinite descent.

I got stuck in this question. Can you help me!
alpah is offline  
December 26th, 2006, 06:31 PM   #2
Global Moderator
CRGreathouse's Avatar
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
You got stuck -- so what do you have so far?
CRGreathouse is offline  
December 27th, 2006, 03:33 PM   #3
Joined: Dec 2006
From: Moscow, Russia

Posts: 4
Thanks: 0

Simple induction on n. n=1 is trivial. Let n>1. By induction sequence is essential constant
modulo phi(n)<n (Euler's totient function).This gives desired result. Just use
If 1)a,,b,c,n are integers,2) n>0, 3)b and c are the same (modulo phi(n)) and 4)b and c are greater than some constant which depends on a and n, then
a^b =a^c (mod n)
R.I.P. is offline  
February 7th, 2007, 04:44 AM   #4
Joined: Jan 2007
From: Hai duong _ vietnam

Posts: 2
Thanks: 0

Oh ; can you use latex ?
mathboy is offline  
February 7th, 2007, 09:59 AM   #5
Senior Member
Joined: Dec 2006

Posts: 1,111
Thanks: 0

No, unfortunately not...
Infinity is offline  

  My Math Forum > Math Forums > Math Events

1991, math, olympiad, question, usa

Thread Tools
Display Modes

Similar Threads
Thread Thread Starter Forum Replies Last Post
Geometry question math olympiad Justme Geometry 3 November 19th, 2013 01:37 AM
Math Olympiad Thailand Niboon Math Events 3 April 3rd, 2013 10:57 AM
any book recommendation for math olympiad please? betelgeuse91 Math Events 4 August 18th, 2011 09:20 PM
Math Olympiad book for Grade 2 to 8 yoyobarn Math Books 1 July 25th, 2009 04:40 PM
1991 usa math olympiad question! alpah Number Theory 0 December 31st, 1969 04:00 PM

Copyright © 2019 My Math Forum. All rights reserved.