Results 1 to 4 of 4

Math Help - Urgent Help needed!

  1. #1
    Newbie
    Joined
    Apr 2006
    Posts
    7

    Urgent Help needed!

    Using the fact that reduction can be carried out at each stage without changing the end result, calculate 43^97(mod 98) exactly using only the capabilites of a standard pocket calculator.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by jzon
    Using the fact that reduction can be carried out at each stage without changing the end result, calculate 43^97(mod 98) exactly using only the capabilites of a standard pocket calculator.
    You can use a theorem called "Euler's Generalization of Fermat's Theorem" which means, that since,
    \gcd(43,98)=1 thus,
    43^{\phi(98)}\equiv 1\mod 98
    Since, \phi(98)=42
    Thus,
    43^{42}\equiv 1\mod 98
    Squaring both sides,
    43^{84}\equiv 1\mod 98 (1)
    --------
    Notice that,
    43^2\equiv 85\equiv -13
    Square,
    43^4\equiv (-13)^2\equiv 71\equiv -27 (2)
    Square,
    43^8\equiv (-27)^2 \equiv 43 (3)
    Mutiply (2) by (3),
    43^{12}\equiv 15 (4)
    Now, multiply (1) by (4),
    43^{96}\equiv 15
    Finally multiply both sides by 43,
    43^{97}\equiv 15\cdot 43\equiv 57
    Thus,
    43^{97}\equiv 57\mod 98

    Without Euler's Theorem this can still be done but only much longer.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2006
    Posts
    7
    Is this the same as Fermat's Little Theorem??? I would appreciate if some1 could give the solution using fermat's little theorem

    THanks
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by jzon
    Is this the same as Fermat's Little Theorem??? I would appreciate if some1 could give the solution using fermat's little theorem

    THanks
    Almost.
    You cannot use Fermat's Little Theorem because 98 is not prime.
    But you can use another:
    "If \gcd(a,n)=1 and \phi(n) is the number of integers relatively prime to n but not exceeding, then,
    a^{\phi(n)}\equiv 1\mod n"

    Also, a formula for calculating the phi-function, with prime factoriztion.
    If n=p_1^{a_1}p_2^{a_2}...p_k^{a_k}
    Then, \phi(n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)....\left(1-\frac{1}{p_k}\right)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. urgent help needed
    Posted in the Algebra Forum
    Replies: 1
    Last Post: January 7th 2009, 12:52 PM
  2. Urgent Help Needed! Any Help Will Do
    Posted in the Business Math Forum
    Replies: 1
    Last Post: October 10th 2008, 05:21 AM
  3. URGENT Help Needed
    Posted in the Algebra Forum
    Replies: 3
    Last Post: July 3rd 2008, 01:08 PM
  4. Urgent Help Needed
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: November 18th 2007, 05:41 PM
  5. urgent help needed!!!!!!!!!
    Posted in the Algebra Forum
    Replies: 5
    Last Post: October 12th 2007, 09:55 AM

Search Tags


/mathhelpforum @mathhelpforum