Results 1 to 3 of 3

Thread: 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 $\displaystyle n,$ an integer $\displaystyle m$ has to satisfy the condition : $\displaystyle \text{gcd}(m,n)=1$

    Now if $\displaystyle n,m$ are relative primes, then you can use Bezout's algorithm to find $\displaystyle u,v$ integers such that : $\displaystyle un+vm=1.$ Thus you'll have $\displaystyle [1]=[un+vm]=[u][n]+[v][m]=[u][0]+[v][m]=[v][m]$ i.e. the class of $\displaystyle 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
    12,028
    Thanks
    848
    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: .$\displaystyle 3276a \:\equiv \:1 \pmod{3025}$

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

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


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

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

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


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

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

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


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

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

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


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

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

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

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


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


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

    Check

    $\displaystyle (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: Jul 9th 2011, 01:52 PM
  2. inverse of modulo
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Jun 22nd 2009, 07:03 PM
  3. (n) inverse modulo m
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Feb 21st 2009, 10:49 AM
  4. Inverse of a modulo
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Oct 3rd 2008, 11:00 AM
  5. inverse modulo
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Sep 15th 2008, 01:31 PM

Search Tags


/mathhelpforum @mathhelpforum