My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
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
alfonso1 is offline  
 
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.
mathman is offline  
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...
alfonso1 is offline  
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.
Infinity is offline  
July 27th, 2007, 11:13 PM   #5
Site Founder
 
julien's Avatar
 
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).
julien is offline  
July 28th, 2007, 08:19 AM   #6
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
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.
CRGreathouse is offline  
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?!!!
alfonso1 is offline  
July 29th, 2007, 01:06 PM   #8
Site Founder
 
julien's Avatar
 
Joined: Nov 2006
From: France

Posts: 824
Thanks: 7

7^1=7, as easy as it sounds
julien is offline  
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?
alfonso1 is offline  
July 29th, 2007, 04:21 PM   #10
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
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.
CRGreathouse is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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





Copyright © 2019 My Math Forum. All rights reserved.