September 24th, 2007, 06:04 PM  #1 
Newbie Joined: Sep 2007 Posts: 7 Thanks: 0  Multiplicative inverse
I just started learning modular arithmetic in my Cryptology class this semester, so this is probably a stupidly basic problem, but how do I explain why (n1)^1 (is congruent to) n1 (mod n) ? I can't even figure out how to prove it, much less explain it. And I have no clue where this would go, but: A monk begins an ascent of Mt. Fuji Monday morning, reaching the summit by nightfall. He spends the night at the summit and starts down again the following morning, reaching the bottom by dusk on Tuesday. Prove that at some precise time of day, the monk was at exactly the same altitude on Tuesday as he was on Monday. All I can think is that he must have been at every possible altitude from zero to Fuji on Monday, and been somewhere at every possible time from morning to nightfall, and likewise for Tuesday, so if you graphed altitude vs. time of day for both days the lines would have to intersect? But my professor does not like graphical proofs. 
September 24th, 2007, 07:14 PM  #2  
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  Re: Multiplicative inverse Quote:
First let me do this chain starting from what I want to prove; that doesn't prove anything, of course, but you can see where I'm going. (n1)^(1) = n1 (mod n) (n1) * (n1)^(1) = (n1)^2 (mod n)  multiply by n1 on both sides 1 = (n1)^2 (mod n)  number * inverse = 1 1 = n^2  2n + 1 (mod n)  simplify 1 = 1 (mod n)  reduce mod n You can see you can start with the last statement as obviously true and work in reverse (check that this works!). Quote:
 
September 24th, 2007, 07:42 PM  #3 
Newbie Joined: Sep 2007 Posts: 7 Thanks: 0 
Okay, thank you! And I got the monk problem. Used a graph but did mention the IVT. 

Tags 
inverse, multiplicative 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
multiplicative inverse in modular arithmetic  amnakhan786  Number Theory  1  November 19th, 2012 03:23 AM 
a multiplicative cipher  milly2012  Number Theory  7  May 28th, 2012 04:17 AM 
multiplicative inverse using Euclid’s Algorithm  mathslog  Number Theory  7  May 25th, 2012 04:47 AM 
Multiplicative function  Fernando  Number Theory  1  April 10th, 2012 07:34 AM 
Every member of a multiplicative group is its own inverse  restin84  Number Theory  0  December 15th, 2011 11:11 AM 