July 27th, 2007, 01:37 PM  #1 
Newbie Joined: Jul 2007 Posts: 8 Thanks: 0  Mudulo exponent
Hi everybody, I'm trying to find out how to find the exponent such that: 7^exponent mod 71 = 1 ??? I appreciate your help in advance Thankfully Alfonso 
July 27th, 2007, 01:44 PM  #2 
Global Moderator Joined: May 2007 Posts: 6,761 Thanks: 696 
The simplest method seems to be trying cases. Your equation is 7^k=71n+1, where k and n are unknown integers. 
July 27th, 2007, 02:00 PM  #3 
Newbie Joined: Jul 2007 Posts: 8 Thanks: 0 
I have been trying the same all the time, but could find that K, I have been trying with Java, but because of overflow problems I get wrong K...

July 27th, 2007, 03:14 PM  #4 
Senior Member Joined: Dec 2006 Posts: 1,111 Thanks: 0 
I've done some number theory work in Java as well, but it requires a special class to handle the huge numbers required. Try looking at the Java documentation for the BigInteger class. Using it will stop all of the overflow errors that you are encountering.

July 27th, 2007, 11:13 PM  #5 
Site Founder Joined: Nov 2006 From: France Posts: 824 Thanks: 7 
71 is prime, therefore 7^70=1 modulo 71 by Fermat's theorem. This is the smallest such exponent because in the cyclic multiplicative group (Z/71Z)*, the order of 7 has to be a divisor of 70 by Lagrange's theorem, but the cases 1, 2, 5, 7, 10, 14, 35 do not work (obvious for 1, 2; you can check the rest by using a calculator; in order to avoid an overflow, use the fact that 7^7=14 modulo 71; therefore you need to check that 14^2<>1 mod 71 and that 14^5<>1 mod 71 in order to rule out the cases 14 and 35, which are the ones inducing overflows).

July 28th, 2007, 08:19 AM  #6 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms 
There's no reason to use a number larger than 4900 = 70^2 when calculating modulo 71. Just reduce (mod 71) at each step. In fact, you don't even have to work with numbers outside the range k <= 35 if you use negatives. 7^1 = 7 (mod 71) 7^2 = 49 = 22 (mod 71) 7^4 = 484 = 11 (mod 71) 7^8 = 121 = 21 (mod 71) etc. You can calculate other numbers mod 71 by multiplying appropriate powers: 7^12 = 7^8 * 7^4 = 11 * 21 = 231 = 18 (mod 71) Of course don't trust my arithmetic, do it yourself. I probably made at least a mistake or two, since I did this entirely in my head. 
July 29th, 2007, 12:51 PM  #7 
Newbie Joined: Jul 2007 Posts: 8 Thanks: 0 
thank you all, I have just last question: how would it be if one would needs to find: 7^exponent = 7 mod 71?!!! 
July 29th, 2007, 01:06 PM  #8 
Site Founder Joined: Nov 2006 From: France Posts: 824 Thanks: 7 
7^1=7, as easy as it sounds 
July 29th, 2007, 01:11 PM  #9 
Newbie Joined: Jul 2007 Posts: 8 Thanks: 0 
well, it'S stated here an exponent larger than 1! any idea?

July 29th, 2007, 04:21 PM  #10 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms 
I think that each number mod 71 has order dividing 711, that is, order in {1, 2, 5, 7, 10, 14, 35, 70}. This means that each element raised to one of those powers is 1 (mod 71), and so 7^(x+1) where x is its order mod 71 is 7. This gives you just 8 numbers to try.


Tags 
exponent, mudulo 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Exponent  Thinkhigh  Calculus  3  March 2nd, 2012 06:42 AM 
Exponent Laws  happysmiles374  Elementary Math  2  February 28th, 2012 08:48 AM 
Exponent Question  xnarutox  Algebra  8  October 7th, 2010 06:41 PM 
variable and the exponent  skarface  Algebra  1  January 24th, 2010 03:28 PM 
Complex exponent  greg1313  Applied Math  3  November 17th, 2009 07:39 PM 