Question

remainder of 3^1990 : 41 is ...

Answer 1

use below :

3^4 leaves a remainder -1

Answer 2

1990 is disable divided by 41, @ganeshi

Answer 3

\(3^{1990} = 3^{497\times 4 + 2} = 3^2 3^{497\times 4} = 9 (3^4)^{497}\)

Answer 4

since \(3^4\) leaves a remainder \(-1\),
\((3^4)^{497}\) leaves a remainder \((-1)^{497}\)

Answer 5

honestly, i m not good in modulo. i dont know which properties i should use

Answer 6

can you show to me step by step to solve this, @ganeshie8

Answer 7

we need to use only two properties :

1) if \(a \) leaves a remainder \(r\), then \(a^n\) leaves a remainder \(r^n\)
1) if \(a \) leaves a remainder \(r\), then \(a\times c\) leaves a remainder \(a\times r\)

Answer 8

you familiar wid congruence notation right ?

Answer 9

yeah, it like
3^1990 mod(41)
= ...

Answer 10

corrected typo..
we need to use only two properties :

1) if \(a\) leaves a remainder r, then an leaves a remainder \(r^n\)
2) if \(a\) leaves a remainder r, then a×c leaves a remainder r×c

Answer 11

ahh then its easy

Answer 12

\(3^{1990} \equiv 3^{4\times 497 + 2} \equiv 3^2 (3^4)^{497}\mod 41 \)

Answer 13

fine so far ?
we hvaent used any mod properties yet... just broke down the exponent...

Answer 14

ok, so far i got
9(81)^497 mod(41)
what's next ?

btw, can you type the equation more big before ?, thanks :)

Answer 15

\(\large 3^{1990} \equiv 3^{4\times 497 + 2} \equiv 3^2 (3^4)^{497}\mod 41 \)

Answer 16

this looks better ?

Answer 17

yeah, that's better than before :)

Answer 18

next, whats the remainder when 3^4 is divided by 41 ?

Answer 19

40

Answer 20

81/41 = 1, remainder 40 right ?

Answer 21

yes,


81/41 :

40 is the overflow
also, -1 is the underflow

Answer 22

saying "40" is the remainder is same as saying "-1" is the remainder

Answer 23

40 - 41 = -1

Answer 24

ah, yes i know because 81-(-1) is multiply of 41, right ?

Answer 25

yes, thats more elegant way of putting it :)

Answer 26

go back to the mod

Answer 27

\(\large 3^{1990} \equiv 3^{4\times 497 + 2} \equiv 3^2 (3^4)^{497} \equiv 9(-1)^{497} \mod 41\)

Answer 28

see if that looks still fine

Answer 29

(-1)^497 = -1
so,
9(-1) mod 41
= -9 mod 41
= ... what's next ?

Answer 30

we're done

Answer 31

-9 is the remainder

Answer 32

-9 is same as -9+41

Answer 33

huh ? -9, it should be positive ?

Answer 34

just add 41 if u want positive answer

Answer 35

ohhhhhhhhhhhh.... im very stupid with this, that's make sense now. before i used binomial newtown's theorem, twhere to longg. but i got same answer. it is 32

Answer 36

thank you very much, @ganeshie8 .
btw, do you know the sites where i get more question to training my self ?

Answer 37

oh interesting, i thought of binomial in the start... but couldn't figure out how the simplification is possible using binomial...

Answer 38

if its not lengthy, may i knw how did u proceed wid the binomial thm ?

Answer 39

same like the 1st.
3^(1990) : 41
= (3)^(4*497 + 2) : 41
= 9 * (3^4)^497 : 41
= 9 * (81)^497 : 41
= 9 * (82-1)^497 : 41

see, that
(82-1)^497 = 497C0 (82)^497 - 497C1 (82)^496 + 497C2 (82)^495 + ... + 497C495(82)^2(-1) + 497C496 (82)(-1)^498 + 497C497 (-1)^497

i assumed that 497C0 (82)^497 - 497C1 (82)^496 + 497C2 (82)^495 + ... - 497C495(82)^2(-1), is P. where obvious this sum able divided by 41. so,

9 * (82-1)^497 : 41
= 9 * [P + 497C496 (82)(-1)^498 + 497C497 (-1)^497] : 41
= 9 * [P + 497 * 82 - 1] : 41
= 9 * [P + 40,753] : 41
= (9P + 9*40,753) : 41
= 9P/41 + (9*40,753 : 41)

(9*40,753 : 41), from here i got the remainder 32 :)

Answer 40

Excellent !!

basically u have simplified it to form :

9 * (82-1)^497 = 9( 82*something - 1)
since 82 is divisible by 41, remainder is -9

Answer 41

but looks, my way is stupid, very-very stupid. too longggggggg :V

Answer 42

noo, its not long.

try below when you're free :
find the remainder when 5^99 is divided by 13

Answer 43

we can do this both ways : mods, and binomial

Answer 44

well, i'll try this :)

Answer 45

5^99 mod(13)
= 5^(2*49 + 1) mod(13)
= 5 * 5^(2*49) mod (13)
= 5 * 25^49 mod (13)
= 5 * (26-1)^49 mod (13)
wait.. what should i do now

Answer 46

\(25 \equiv -1 \mod 13 \)

Answer 47

5^99 mod(13)
= 5^(2*49 + 1) mod(13)
= 5 * 5^(2*49) mod (13)
= 5 * 25^49 mod (13)
= 5 * (-1)^49 mod (13)

Answer 48

binomial thm is also easy here..

Answer 49

5 * (26 * something - 1)
since 26 is divisible by 13, remainder is -5
haha.. i copied your statement :)

Answer 50

yup :) both methods give answer in one step !!

Answer 51

here more problems :

http://www.mathdb.org/notes_download/elementary/number/ne_N2.pdf

Answer 52

so, then
just add -5 with 13 ?

Answer 53

yes !

Answer 54

8 is the remainder

Answer 55

try Example 1.1 problems in above link when ur free... have fun :)

Answer 56

waaw, math is beatiful. i dont know before, if i get negative then just add with divisor

Answer 57

number theory is beautiful and easy if we use intuition enough :)

yes, also saying "-5" is remainder is perfectly fine as well.

more on this here :
http://openstudy.com/users/ganeshie8#/updates/533ef9e1e4b05a4f7d53c3ee

Answer 58

thank you so much, for your helps and for the links. i;ll try those later ...
:)

Answer 59

np :)

Answer 60

just wanna quick confirmation are you trying to find the remainder of
\[3^{1990} (\mod 41)\]?

because i got a different remainder

Answer 61

yeah, i got 32

Answer 62

oh sorry nvm i looked i the wrong posts lol
yea i got 32 as well

i wanna gonna suggest using Fermat's Little Theorem to do this problem

Answer 63

^Fermat is the fastest way

Answer 64

To confirm your answer visit
http://www.wolframalpha.com/input/?i=remainder+%28+3^1990%2C+41%29