User Name Remember Me? Password

 Number Theory Number Theory Math Forum

 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,704 Thanks: 669 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 71-1, 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 Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post Thinkhigh Calculus 3 March 2nd, 2012 06:42 AM happysmiles374 Elementary Math 2 February 28th, 2012 08:48 AM xnarutox Algebra 8 October 7th, 2010 06:41 PM skarface Algebra 1 January 24th, 2010 03:28 PM greg1313 Applied Math 3 November 17th, 2009 07:39 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top      