Results 1 to 3 of 3

Math Help - Inverse Modulo

  1. #1
    Newbie
    Joined
    Feb 2009
    Posts
    4

    Inverse Modulo

    a: With justification, find an inverse for 3276 modulo 3025.
    b: With justification, find an inverse for 3276 modulo 3026.

    I am completely stumped
    How can there be a positive integer 's' such that 3276 ∙ s ≡ 1 (mod 3025 (or 3026)) ???
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    Hi
    First of all, to have its class inversible modulo n, an integer m has to satisfy the condition : \text{gcd}(m,n)=1

    Now if n,m are relative primes, then you can use Bezout's algorithm to find u,v integers such that : un+vm=1. Thus you'll have [1]=[un+vm]=[u][n]+[v][m]=[u][0]+[v][m]=[v][m] i.e. the class of v will be your inverse.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,657
    Thanks
    598
    Hello, starman_dx!

    There are a number of streamlined procedures.
    I'll show you a primitive algebraic approach.


    (a) With justification, find an inverse for 3276 modulo 3025.
    We have: . 3276a \:\equiv \:1 \pmod{3025}

    This means: . 3276a \:=\:3025b + 1\:\text{ for some integer }b.

    Solve for b\!:\;\;b \:=\:\frac{3276a - 1}{3025} \quad\Rightarrow\quad b \:=\:a + \frac{251a - 1}{3025}


    Since b is an integer, 251a - 1 is a multiple of 3025.

    . . That is: . 251a - 1 \:=\:3025c\:\text{ for some integer }c,

    Solve for a\!:\;\;a  \:=\:\frac{3025c + 1}{251} \quad\Rightarrow\quad a \:=\:12c + \frac{13c+1}{251} .[1]


    Since a is an integer, 13c+1 is a multiple of 251.

    . . That is: . 13c + 1 \:=\:251d\:\text{ for some integer }d.

    Solve for c\!:\;\;c \:=\:\frac{251d - 1}{13} \quad\Rightarrow\quad c \:=\:19d + \frac{4d-1}{13} .[2]


    Since c is an integer, 4d-1 is a multiple of 13.

    . . That is: . 4d-1 \:=\:13e\:\text{ for some integer }e.

    Solve for d\!:\;\;d \:=\:\frac{13e+1}{4} \quad\Rightarrow\quad d \:=\:3e + \frac{e+1}{4} .[3]


    We see that d is first an integer when e = 3.

    Substitute into [3]: . d \:=\:3(3) + \frac{3+1}{4}\quad\Rightarrow\quad d \:=\:10

    Substitute into [2]: . c \:=\:19(10) + \frac{4(10)-1}{13} \quad\Rightarrow\quad c \:=\:193

    Substitute into [1]: . a \:=\:12(193) + \frac{13(193) + 1}{251} \quad\Rightarrow\quad a \:=\:2326


    Therefore, the inverse of 3276\:(\text{mod }3025) is: . \boxed{2326}


    ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

    Check

    (3276)(2326) \;=\;7,\!619,\!876 \;=\;(3025)(2519) + 1

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] inverse in modulo 26
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 9th 2011, 01:52 PM
  2. inverse of modulo
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 22nd 2009, 07:03 PM
  3. (n) inverse modulo m
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 21st 2009, 10:49 AM
  4. Inverse of a modulo
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 3rd 2008, 11:00 AM
  5. inverse modulo
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: September 15th 2008, 01:31 PM

Search Tags


/mathhelpforum @mathhelpforum