Question

What is the remainder when you divide 4^44 by 19?

Answer 1

Most of the remainder problems thus far have been simple (square for difference of 1 etc) but I'm not sure how to tackle this one.

Answer 2

Using mod and congruences

Answer 3

A similar process: http://gmatclub.com/forum/what-is-the-remainder-when-43-86-is-divided-by-134778.html

Answer 4

Is there an easy way to go about this besides guessing and checking numbers?

Answer 5

There might be, but sadly, I am not very familiar with this process. ^^;
Perhaps someone else can assist you? :]

Answer 6

with this type of equation*

Answer 7

there are several ways to do this, one easy mehtod that doesn't require much theory is binary exponential algorithm

heard of it before ?

Answer 8

No I haven't, sorry.

Answer 9

Notice 44 = 32 + 8 + 4

Answer 10

4^2 = 16 = -3
`4^4 = (-3)^2 = 9`
`4^8 = 9^2 = 5`
4^16 = 5^2 = 6
`4^32 = 6^2 = -2`

Answer 11

\[4^{44} = 4^{32+8+4} = 4^{32}\cdot 4^8\cdot 4^4 \equiv -2\cdot 5\cdot 9 \equiv 5 \]

Answer 12

strange

Answer 13

Okay, that's amazing thank you. Can I ask how you reasoned through that though? Like, each step makes sense, but I would have no idea how to replicate that during an exam.

Answer 14

i thought fermat little theorem is efficient

Answer 15

Yep fermat little thm gives the answer fast

Answer 16

lets do another problem and im sure you will see why this works

Answer 17

\(\large \begin{align} \color{black}{\normalsize \text{one easy way is to apply fermat's little theorem}\hspace{.33em}\\~\\
a^{n-1}\pmod n=1,n\nmid a \hspace{.33em}\\~\\
\dfrac{4^{44} }{19}\hspace{.33em}\\~\\
=\dfrac{4^{19\times 2}\cdot 4^{8} }{19}\hspace{.33em}\\~\\
=\dfrac{1\cdot 4^{8} }{19}\hspace{.33em}\\~\\
=\dfrac{1\cdot 16^{4} }{19}\hspace{.33em}\\~\\
=\dfrac{ (-3)^{4} }{19}\hspace{.33em}\\~\\
=\dfrac{ (9)^{2} }{19}\hspace{.33em}\\~\\
=\dfrac{ 81 }{19}\hspace{.33em}\\~\\
=\dfrac{5}{19} \hspace{.33em}\\~\\
=5 \hspace{.33em}\\~\\
}\end{align}\)

Answer 18

We haven't used Fermat's Little Theorem yet.

Answer 19

i m still unable to understand ur computer algorithm

Answer 20

and how can it work on every \(\pmod n\) ?

Answer 21

note that \(n\) id prime is my answer

Answer 22

And ganeshie, that was the last problem of its kind. There's one last proof dealing with mods that I'm not sure how to tackle if ya want to be an incredible human being again and explain

Answer 23

It's different, but also pretty complicated. I need to prove that 4^n is congruent to 1+3n (mod 9)

Answer 24

I feel like with a lot of these mod problems I'm able to look at the answer once it's given and be like "oh okay, every step makes sense. No idea how they got from start to finish without blind guessing though"

Answer 25

might be helpful
https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic

Answer 26

Thank you, bookmarked it for later.

Answer 27

I don't have a ton of time left before I've got to drive to classes though, and I still feel like I have no idea how to proceed with this proof. Do you have any ideas?

Answer 28

for fermat liite theorm ?

Answer 29

You and Gane have been amazing by the way, sorry to have needed so much help.

Answer 30

It should be easy using binomial thm. Just write 4 as 3+1 and expand

Answer 31

No uhh "If Prove 4n ≡ 1 + 3n (mod 9) for any integer n ≥ 1"

Answer 32

might be helpful
https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic

Answer 33

Prove 4n is congruent to 1+ 3n mod 9

Answer 34

Okay 1 second gane

Answer 35

what is n here ?

Answer 36

A number greater than 1

Answer 37

Integer*

Answer 38

\[\begin{align}4^n = (1+3)^n &= \binom{n}{0} 1^n3^0 + \binom{n}{1} 1^{n-1}3^1 +
3^2(\text{stuff}) \\~\\
&= 1 + 3n + 9(\text{stuff}) \\~\\
&\equiv 1+3n + 0 \pmod{9}
\end{align}\]

Answer 39

oh its exponent

Answer 40

Oh sorry. The copy paste kinda failed the second time.
Yeah. It's 4^n is congruent to 3n+1 mod 9

Answer 41

perfect!

Answer 42

I haven't seen that
(n
0 )
Notation. But if I understand the proof I'm going to have to show that 3^n = 3n mod 9 and it basically cylces for values of n?

Answer 43

(not at all very well written, but does that sound close to right?)

Answer 44

familiar with binomial thm ?

Answer 45

No, not really.

Answer 46

https://www.mathsisfun.com/combinatorics/combinations-permutations.html

Answer 47

Binomial theorem is the first thing to learn in number theory
http://en.wikipedia.org/wiki/Binomial_theorem

Answer 48

It is so fundamental and important.. Most proofs and concepts in number theory depend on / use binomial thm

Answer 49

I checked the references, and binomial theorem isn't show in our text until a couple chapters down the line, and our professor hasn't discussed it yet, so for now I have to make due without it.

Answer 50

makes no sense to study congruences w/o covering binomial thm first

Answer 51

yes binomial is very important

Answer 52

(im just saying that to stress the importance of binomila thm haha!)

Answer 53

i said beacause that is really cool and important

as i never studied mod arithmatic , just used applications of binomial through out

Answer 54

Indeed it is cool and wont take much time to learn/use it

Answer 55

But you will be amazed by the complicated problems that it allows you to solve.. !

Answer 56

Alright, I'll be sure to look in to it later tonight.

Answer 57

What textbook are you using ?

Answer 58

Elementary Number Theory and its Applications - Kenneth H Rosen 6th edition

Answer 59

Just to make sure, I basically need to show 3^n = 3n mod 9 right?

Answer 60

thats not true, try n=2

Answer 61

3^2 = 3*2 mod 9

9 = 6 mod 9

0 = 6 mod 9

false

Answer 62

Okay right. Sorry

Answer 63

you need to know binomial thm to understand above proof... let me see if we can avoid it :)

Answer 64

we may try induction

Answer 65

Induction seems odd. Or maybe I just don't understand cause I'm new at this, but doesn't it change for every n+1?

Answer 66

i didnt get that.. what do you mean by change for every n+1 ?

Answer 67

Umm. Nevermind. You go ahead and explain and I'll see if I don't follow anything.

Answer 68

Induction is pretty straightforward and simple as we always know where to start

Answer 69

I'm only here 'cos notifications will break my computer. ; o;

Answer 70

It's cool Kitti. I got to go in 15 minutes so hopefully this isn't on too much longer.

Answer 71

Alright xD

Answer 72

To prove : \(4^n \equiv 3n+1 \pmod{9}\)

Base case : \(4^1 = 4 = 3*1+1 \pmod{9}~\color{green}{\checkmark}\)

Induction step : Assume \(4^k\equiv 3k+1\pmod{9}\) is true.
\[4^{k+1}\equiv 4\cdot 4^k\equiv 4(3k+1) = 12k+4 \equiv 3k+4 = 3(k+1)+1\pmod{9} \]

\(\blacksquare\)

Answer 73

Okay, that's incredible. You're amazing, thank you so much.

Answer 74

ganeshie = the Math God of OS

Answer 75

and hartnn ofc

Answer 76

\(\large \color{magenta}{\heartsuit }\)

Answer 77

:)

Answer 78

Okay, again, thank you so much Gane and mathmath for all your help today. You both are incredible