Question

What is the remainder when 2^33 is divided by 17?

Answer 1

maybe first find 2^33

Answer 2

really?
you think i should do that tedious work?
it can't be that straight..

Answer 3

what else have you tried ?

Answer 4

i know .. its more like some theorem

Answer 5

aren't you too young to be familiar with modular arithmetic and/or binomial theorem?

Answer 6

@parth I dunno it is from my textbook:(

Answer 7

so then you're not familiar with any of those?

Answer 8

@ganeshie8 I tried the cyclicity but that doesn't give any clue at all.....
@ParthKohli What ya mean?

Answer 9

binomial theorem
modular arithmetic
do you know any of these?
and yes, the cyclic nature of remainders should give a nice hint

Answer 10

thats not a bad attempt!

familiar with below property ?

If \(a\) leaves a remainder \(r\) when divided by \(b\),
then \(a^k\) leaves a remainder \(r^k\) when divided by \(b\)

Answer 11

for example :

\(5\) leaves a remainder \(1\) when divided by \(4\),
therefore \(5^3\) leaves a remainder \(1^3\) when divided by \(4\)

Answer 12

you might need something like binomial theorem to prove above property

Answer 13

@ParthKohli I am not familiar with any of those:(
and @ganeshie8 I dunno that property but yeah..that gives some insight...

Answer 14

u shuold study negative remainders then this questions will be easy

Answer 15

negative remainders?
okay @ganeshie8 so if 2 leaves a remainder 15 when divided by 17,therefore 2^33 leaves a remainder 15^33 when divided by 17???:/

Answer 16

@ParthKohli what hint from cyclicity please?

Answer 17

observe that \(2^4\) leaves a remainder \(-1\) when divided by 17.
or better, \(2^8\) leaves a remainder \(1\) when divided by 17.
whenever you get a remainder of 1, the remainders begin to repeat themselves.

Answer 18

@ParthKohli
'whenever you get a remainder of 1, the remainders begin to repeat themselves.'
What does this mean?I dun understand:(

Answer 19

a simpler example would be this: remainders of powers of 2 when divided by 5.
2^1: 2
2^2: 4
2^3: 3
2^4: 1
2^5: 2
2^6: 4
2^7: 3
2^8: 1

do you see how it's going like 2, 4, 3, 1, 2, 4, 3, 1...? and the last number of every cycle is always 1.

Answer 20

\(\large \color{black}{\begin{align}
&\dfrac{2^{33}}{17}\hspace{.33em}\\~\\
&\implies \dfrac{2^{33}}{17}\hspace{.33em}\\~\\
&\implies \dfrac{2\cdot 2^{32}}{17}\hspace{.33em}\\~\\
&\implies \dfrac{2\cdot 4^{16}}{17}\hspace{.33em}\\~\\
&\implies \dfrac{2\cdot 16^{8}}{17}\hspace{.33em}\\~\\
&\implies \dfrac{2\cdot (-1)^{8}}{17}\hspace{.33em}\\~\\
&\implies \dfrac{2\cdot 1}{17}\hspace{.33em}\\~\\
&\implies 2\hspace{.33em}\\~\\
\end{align}}\)

Answer 21

2^33 can be written as 2(16)^8 and that can be simplified as 2(17-1)^8 now apply binomial u wil get it..

Answer 22

Well @mathmath I dun understand the last step..the one where you replaces 16^8 with (-1)^8 since I dun know what ever method you have applied there.I used the clue given by @ParthKohli in order to procure the answer and got 2 that is the same as yours..but my textbook says 15 which is really weird since 2 seems correct....

Answer 23

@samigupta8 I am not familiar with the binomial theorem...but thanks for lending a hand here:)

Answer 24

if (a-1) is divided by a where a>1 and is a natural numberthen remainder can be written as -1

Answer 25

Ok..no problem..well the most apt way is then as given by parth so u should follow the multiplicity part only..and 2 is right ans ..

Answer 26

Okay...so I got it!Maybe it is a misprint in my textbook
Thanks everyone:)
and @ParthKohli thanks for the simple example..made it much easier to understand:)

Answer 27

I think Fermat's little theorem is good for this problem

Answer 28

@Vijeya3
https://en.wikipedia.org/wiki/Fermat's_little_theorem

Answer 29

@mayankdevnani
honestly?I couldn't make head or tail of that theorem..
Anyways,thanks for lending a hand here

Answer 30

abe dafod !
main kisliye hoon pgir

Answer 31

*phir

Answer 32

chambal main kudd gayi kya ?

Answer 33

:(
main duffer kyu?
wese pata tha...phele se hi

Answer 34

maine kab kaha tum daffar hoon ?
arrey yeh toh mazak tha bulane ke liye
sorry agar tumhe bura laga ho toh

Answer 35

LOL
wow!ese hi bulaya karo..kam se kam sun toh leti hu:P
and yeah..i didn't get offended..sunne ki aadat h:P

Answer 36

let's start

Answer 37

hmm..okay
warning-and if i don't understand ,dun get annoyed..m hard at grasping

Answer 38

pehle wikipedia pr doosra formula pado

Answer 39

dekho...wo statement samjh me aa gaya..but i dun understand that mod and all

Answer 40

mod aise hi cheez hain...faltu ki

Answer 41

LOL
then wut is the significance of that?

Answer 42

baad main pata chal jayega

Answer 43

ab dekho, p=17 lo
kyunki mod ke peeche jo bhi cheez aayegi woh divisior hogs

Answer 44

*hoga

Answer 45

if she knew modular arithmetic, then she wouldn't need to know fermat's little theorem...

Answer 46

there are 3 methods :-
1)Binomial Theorem
2)Cyclicity
3) Fermat's little theorem

Answer 47

she doesn't know 1st.
She knows 2nd
and i teach her 3rd

Answer 48

ek baar solve kariyo using FLT?

Answer 49

haan
kyun nahi

Answer 50

let p=17
apply prime no divisibility method,
\[\large \bf 2^{17-1}=1 \mod 17\]
\[\large \bf 2^{16}=1 \mod 17\]
since 32 is perfectly divisible by 32,
so
\[\large \bf 2^{32}=1 \mod 17\]
multiply both sides by 2,
\[\large \bf 2^{33}=2 \mod 17\]
Hence, 2 is remainder

Answer 51

typo
correction:-
since 32 is perfectly divisible by 16

Answer 52

you applied many more properties of modular arithmetic.
i think if we just teach her those properties of modular arithmetic, then it'd be easier to solve. FLT is just an added burden.\[2^{33} \equiv 2\cdot(2^4)^8 \equiv 2\cdot(-1)^8 \equiv 2 \pmod{17}\]

Answer 53

cyclicity is best for her level now

Answer 54

aur kya -_-

Answer 55

-_-
wow

Answer 56

vijeya try these

2^31 is divided by 17

Answer 57

@mathmath333 9?

Answer 58

how u get there