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
September 24th, 2007, 07: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

(n-1)^-1 (is congruent to) n-1 (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.
nightshadengale is offline  
 
September 24th, 2007, 08:14 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
Re: Multiplicative inverse

Quote:
Originally Posted by nightshadengale
(n-1)^-1 (is congruent to) n-1 (mod n) ? I can't even figure out how to prove it, much less explain it.
I'll use = here for "is congruent to".

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.
(n-1)^(-1) = n-1 (mod n)
(n-1) * (n-1)^(-1) = (n-1)^2 (mod n) -- multiply by n-1 on both sides
1 = (n-1)^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:
Originally Posted by nightshadengale
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.
The monk's path is continuous, so the two functions must intersect. If you have the intermediate value theorem you can use this on the difference of the functions.
CRGreathouse is offline  
September 24th, 2007, 08: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.
nightshadengale is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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 04:23 AM
a multiplicative cipher milly2012 Number Theory 7 May 28th, 2012 05:17 AM
multiplicative inverse using Euclid’s Algorithm mathslog Number Theory 7 May 25th, 2012 05:47 AM
Multiplicative function Fernando Number Theory 1 April 10th, 2012 08:34 AM
Every member of a multiplicative group is its own inverse restin84 Number Theory 0 December 15th, 2011 12:11 PM





Copyright © 2018 My Math Forum. All rights reserved.