fermat's little theorem

**hmmmm** · May 15th 2010, 02:42 PM

find the remain 17der of 36^(50) + 31^(19) when divided by 17, i got 9 for this but apparently the answer is 11, thanks for any help

**Dinkydoe** · May 15th 2010, 02:59 PM

Have you actually used fermat's Little theorem?

It states that for any prime number $p$ we have $a^{p-1}\equiv 1$ mod $p$

Here we divide by $p=17$ , thus we have $a^{16}\equiv 1$ mod 17 for any number $a$ .

Use this fact and observe that $36^{50}\equiv 2^{50} \equiv (*) 2^{2} \equiv 4$ mod 17

(*) here we used fermat's theorem.

Now you try $30^{19}$ mod 17

**undefined** · May 15th 2010, 03:00 PM

Originally Posted by hmmmm

find the remain 17der of 36^(50) + 30^(19) when divided by 17, i got 9 for this but apparently the answer is 11, thanks for any help

$36^{50} + 30^{19} \equiv 2^{50} + 13^{19} \equiv 2^{3\cdot16+2}+13^{16+3} \equiv 2^2+13^3\equiv4+2197\equiv8\ \text{(mod }17\text{)}$

The book answer is 11? I did a direct calculation and also got 8.

**Dinkydoe** · May 15th 2010, 03:08 PM

$36^{50} + 30^{19} \equiv 2^{50} + 13^{19} \equiv 2^{3\cdot16+2}+13^{16+3} \equiv 2^2+13^3\equiv4+2197\equiv8\ \text{(mod }17\text{)}$
The book answer is 11? I did a direct calculation and also got 8.

Yeah me too, 11 is definately wrong!

**hmmmm** · May 15th 2010, 03:46 PM

ok i've checked my answer an i think i made a stupid mistake at the end,

36= 2 mod 17 and 31 = -3 mod 17 therefore

36^(50) + 30^(19) = ( 2^50 + ((-3)^19 ) mod 17
= (1 + -27) mod 17 using fermat's little theorem
= 8 mod 17
therefore the remainder is 8 (i had 9 here instead making a stupid mistake) is this correct then,

really sorry i dont know how to use latex yet but i have my exams soon so im busy revising, thanks for any help

**undefined** · May 15th 2010, 03:56 PM

Originally Posted by hmmmm

ok i've checked my answer an i think i made a stupid mistake at the end,

36= 2 mod 17 and 31 = -3 mod 17 therefore

36^(50) + 30^(19) = ( 2^50 + ((-3)^19 ) mod 17
= (1 + -27) mod 17 using fermat's little theorem
= 8 mod 17
therefore the remainder is 8 (i had 9 here instead making a stupid mistake) is this correct then,

really sorry i dont know how to use latex yet but i have my exams soon so im busy revising, thanks for any help

Is it $36^{50} + 3\color{red}0\color{black}^{19}$ or $36^{50} + 3\color{red}1\color{black}^{19}$ ??

**hmmmm** · May 15th 2010, 04:06 PM

oh dear sorry its 31

**undefined** · May 15th 2010, 04:12 PM

Originally Posted by hmmmm

oh dear sorry its 31

Ah, it's clear now.

-27 is fine. This becomes 7 (mod 17). But where you wrote 1 + -27, it should be 4 + -27. See above posts. Then 4 + 7 = 11.

**hmmmm** · May 15th 2010, 04:20 PM

ah ok thanks very much sorry about that

Thread: fermat's little theorem

LinkBack

Thread Tools

Display

fermat's little theorem

Similar Math Help Forum Discussions

Fermat's little theorem

abstract algebra [primitive root mod n, euler theorem, fermat theorem]

Fermat's Little Theorem

Fermat's Little Theorem Help

Fermat’s Little Theorem

Search Tags