Question

remainder for 3^124/17

Answer 1

3^3 = 10 mod 17 ok ?

Answer 2

book says remainder 4

Answer 3

its 4 :P but do u have any method to solve it ?

Answer 4

(ax+1)^n/a gives remainder 1

Answer 5

(81)^31/17

Answer 6

(85-4)^31

Answer 7

nice :)

Answer 8

but that wont be useful cuz the last term would be (-4)^31

Answer 9

try ikram's method
atleast you will be able to take powers of 10 easily :)

Answer 10

(3^7)^17 will leave the same remainder when divided by 17 as 3^7, so we can address 3^7 · 3^5 = 3^12

And since 3^12 has remainder 4 when divided by 17, so will 3^124
PLEASE EXPLANE THE ABOVE

Answer 11

id like to try ikram's method first :

\[\large 3^{124} = 3^{3\times 40 + 4} = 3^4*27^{40} \equiv 3^4*10^{40} \]

Answer 12

THE original question was 54^124/17 which reduces to 3^124/17

Answer 13

\[\large \begin{array} \\ 3^{124} = 3^{3\times 40 + 4} = 3^4*27^{40} &\equiv 3^4*10^{40} \\
&\equiv 3^4*100^{20}\\
&\equiv 3^4*(-2)^{20} \\
&\equiv 3^4*(-2)^{4\times 5} \\
&\equiv 3^4*(16)^{ 5} \\
&\equiv 3^4*(-1)^{ 5} \\
&\equiv -3^4 \\

\end{array}\]

Answer 14

see if that looks okay so far ^^

Answer 15

can the (-4)^31/ 17 solved further ?

Answer 16

Oh yes ! that gives you answer much faster !

Answer 17

\[\large (-4)^{31} = (-4)^{2\times 15 + 1} = -4 (-4)^{2\times 15} = -4(16)^{15}\]

Answer 18

\[\large \equiv -4(-1)^{15}\]

Answer 19

thats easy

Answer 20

\[\large \equiv -4(-1) = 4\]

yep :)

Answer 21

nico

Answer 22

i just rememberd that

3^16=1 mod 17
xD

Answer 23

but thought he only use like calculation stuff

Answer 24

i think only ppl who take number theory knw about fermat

Answer 25

xD but its cool isnt it :P
i mean whats the point of calculation while we have fermat <3

Answer 26

3^16 = 1 mod 17 may throw off other students,
@mathmath333 do you want to know why 3^16/17 gives you 1 as remainder ?

Answer 27

=o

Answer 28

exactly ! if he knows fermat already, there is no point

Answer 29

well ,i dont know the modulo method lol

Answer 30

Fair enough ! binomial expansion is powerful, but it works only in special cases... modulo method is more universal

Answer 31

can u give link for learning modulo method

Answer 32

if u have time, i can teach u... it only takes 30 minutes to see the beauty of congruences !

Answer 33

:o lol that would be cool to see how u do it in 30 mnts

Answer 34

ya

Answer 35

ok start the clock

Answer 36

it all starts with \(1\) definition and \(5\) theorems :

Definition :
\(\large a \equiv b \mod n\)
means
\(\large a-b\) is divisible by \(\large n\)

Answer 37

whats that 3 lines means

Answer 38

new post :o

Answer 39

for example :
\[\large 11\equiv 1 \mod 10\]

cuz \(\large 11-1\) is divisible by \(\large 10\)

Answer 40

you can read \(\large \equiv \) as `congruent to`

Answer 41

congruency i guess

Answer 42

yes ^^

Answer 43

time pasing :P
continue

Answer 44

ok

Answer 45

let me know once you're happy with the definition

Answer 46

ya i got it defn

Answer 47

fre more examples :

\[\large 7 \equiv 1 \mod 6\]
\[\large 100 \equiv 1 \mod 99\]
\[\large 23 \equiv -1 \mod 24\]

Answer 48

ok

Answer 49

all above examples must make sense before we dive into the \(5\) theorems

Answer 50

basically, we only need to stick to above definition to understand ANYTHING in congruences/modulo world

Answer 51

ready for first theorem ? :)

Answer 52

yes

Answer 53

Theorem 1 :
if \(\large a\equiv b \mod n\) and \(\large c\equiv d \mod n\), then :
\(\large a+c \equiv b+d \mod n\)
\(\large ac \equiv bd \mod n\)

Answer 54

ok

Answer 55

Is the statement of theorem clear ?

Answer 56

lets see an example

Answer 57

yaa

Answer 58

do you want to try and cook up an example ? :)

Answer 59

yes of cos

Answer 60

good, make some example..

Answer 61

I'll give you first example, maybe you can create the next example :)

Answer 62

we know that :
\(3 \equiv 1 \mod 2\)
\(2 \equiv 0 \mod 2\)

so, by Theorem 1 :
\(3+2\equiv 1+0 \mod 2\)

Answer 63

7=1 mod 6 and 13=7 mod 6

Answer 64

yes, thats a good example ^^
apply Theorem 1, what do u get ?

Answer 65

7+13=6+7

Answer 66

dont forget the mod symbol :
7+13=1+7 mod 6

Answer 67

okk

Answer 68

Theorem1 just says this :
Sum of two numbers leaves the same reamainder as the sum of remainders of individual numbers

Answer 69

7+13=1+7 mod 6
20 = 8 mod 6

is this statement correct ? verify the definition

Answer 70

yaa

Answer 71

wait

Answer 72

20 = 8 mod 6
means
20-8 is divisible by 6

thats the definition, right ?

Answer 73

Is 20-8 divisible by 6 ?

Answer 74

nooooooo

Answer 75

why not

Answer 76

20-8 = ?

Answer 77

it leaves remainder

Answer 78

20-8 = 12

are you saying 12 leaves a remainder when divided by 6 ?

Answer 79

oh sry

Answer 80

i tjought 20-6

Answer 81

Theorem 1 is a theorem !
and a theorem can NEVER fail.

Answer 82

lets do one more example using theorem 1

Answer 83

yaa

Answer 84

5 = 1 mod 4
16 = 0 mod 4

apply Theorem 1