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
    10
    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
    10
    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, 01:52 PM
  2. Urgent Help Needed! Any Help Will Do
    Posted in the Business Math Forum
    Replies: 1
    Last Post: October 10th 2008, 06:21 AM
  3. URGENT Help Needed
    Posted in the Algebra Forum
    Replies: 3
    Last Post: July 3rd 2008, 02:08 PM
  4. Urgent Help Needed
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: November 18th 2007, 06:41 PM
  5. urgent help needed!!!!!!!!!
    Posted in the Algebra Forum
    Replies: 5
    Last Post: October 12th 2007, 10:55 AM

Search Tags


/mathhelpforum @mathhelpforum