Modulus and Exponents

The question:

Determine $N$ where $0$ $\leq$ $n$ $\leq$ $16$ such that $710^{447}$$\equiv n ( mod 17 ) My attempt 710^{1} \equiv 710 (mod 17) \equiv 13 710^{2} \equiv 13^{2} \equiv 169 (mod 17) \equiv 16 710^{3} \equiv 16*13 \equiv 208 (mod 17) \equiv 4 710^{4} \equiv 16^{2} \equiv 256 (mod 17) \equiv 1 710^{5} \equiv 16^{2}*13 \equiv 3328 (mod 17) \equiv 13 710^{6} \equiv 4^{2} \equiv 16 (mod 17) \equiv 16 710^{7} \equiv 16*4*13 \equiv 832 (mod 17) \equiv 16 It follows,$$710^{3(149)}\equiv4^{148+1}\equiv4^{148}*4^{1}\equiv4^{2(74)} *4^{1}4^{2(74)}*4^{1}\equiv4^{8}*4^{5(7)}*4^{5(7)}*4^{5(7)}*4^{5(7)}*4^{1}65536 (mod 17) \equiv 1$$So,$$4^{8}*4^{5(7)}*4^{5(7)}*4^{5(7)}*4^{5(7)}\equiv4^{140}$$And,$$4^{140}\equiv4^{4*5*7}$$Since$$4^{4}=256$$We obtain$$256 (mod 17) \equiv 1$$and,$$1^{5*7}=1$$Thus,$N$=$1$• I expanded$4^{2(74)}$and$4^{2}*4^{2}*4^{2}*4^{2}$. – Prime Jul 1 '18 at 22:48 • The$4^{8}$cancels out, since it's modulus is 1 when we substitute.$4^{8}$mod$17=1$. – Prime Jul 1 '18 at 23:01 • You're absolutely right, the only problem is the single missing factor of 4. – David Diaz Jul 1 '18 at 23:03 • Haha I'm off by a whole factor of$4$. I don't really see where, can you point it out? I'm confused by my own work laughs nervously... – Prime Jul 1 '18 at 23:04 • Once you get$710^4 \equiv 1 \mod 17$you are soooooooo golden!. That means$710^{447} = (710)^4*(710)^4*..............*(710)^4*710^3 \equiv 1*1*1*......*1*4\equiv 4 \mod 17$. Don't bother with any higher powers (actually that's always good advice). – fleablood Jul 1 '18 at 23:16 4 Answers Do you know Fermats Little theorem that states if$p$is prime (as$17$is) and$a\not \equiv 0 \mod p$then$a^{p-1} \equiv 1 \mod p$. So$710^{447}= 710^{16k + m} \equiv 710^{16k}710^m \equiv 710^m \mod 17$. If not:$710 = 41*17 + 13 \equiv 13\equiv -4 \mod 17$. ($4$is a much nicer number than$13$).$710^2 \equiv (-4)^2 = 16 \equiv -1 \mod 17$. ($1$is as nice as you can get.)$710^4 \equiv (-1)^2 \equiv 1 \mod 17$.$710^{444} = (710^4)^{111} \equiv 1^{111}\equiv 1 \mod 17$. So$710^{447}\equiv 1*710^3 \equiv (-4)^3 \equiv (-4)^2*(-4)\equiv (-1)*(-4) \equiv 4 \mod 17$. But, yes, what you did looks okay but there's an error somewhere. .... Once your realize that$710^4 \equiv 1 \mod 17$it may, or may not, be worth noting that$710^{4k} \equiv 1 \mod 17; 710^{4k + 1} \equiv 13 \mod 17; 710^{4k +2} \equiv 16 \mod 17; 710^{4k + 3}\equiv 4 \mod 17$. And that is all of the congruences • I am aware of Fermat's Little Thm. and its results, but I don't think my professor would like that...he's a bit of a stickler in that way, I guess. And I didn't see the application for this, until now. Good intuition. Now I need to really analyze exactly what you did... – Prime Jul 1 '18 at 23:08 • Well, all I did was take powers of$(-4)$until I got$(-4)^4 \equiv 1 \mod 17$. And that lets me say$(-4)^{4k}\equiv 1 \mod 17$. So$447 = 444 + 3$so$(-4)^{447}\equiv (-4)^{3} \mod 17$. – fleablood Jul 1 '18 at 23:12 • Basically I did what you did but I was a bit more focused. – fleablood Jul 1 '18 at 23:13 • Also, you were more efficient. Good work. I see you around MSE a lot...👀 – Prime Jul 1 '18 at 23:14 • Yuck. What is k and m? – William Elliot Jul 2 '18 at 2:45 710 = 41 * 17 + 13 = 42 * 17 - 4 447 = 27 * 16 + 15 As 710 /= 0 (mod 17), by Fermat's little theorem 710^16 = 1 (mod 17). Thus 710^447 = (-4)^15 (mod 17) -4 * (-4)^15 = 1 (mod 17); -4 * 4 = 1 (mod 17) (-4)^15 = 4 (mod 17) since$Z_{17}$is a field. 710^447 = 4 (mod 17) If you have$710^4=1$mod$17$it implies that$710^{4n}=1$mod$17$, since$447=444+3=4(111)+3$, you deduce that$710^{447}=710^3$mod$17= 3$mod$17$. • How do you know that is the correct mod? That is a ridiculous computation (I am speaking about$710^{4}$) How can we simplify this better? – Prime Jul 1 '18 at 22:52 • If$710^4=1$mod$17$,$710^8=710^4\times 710^4 =1\times 1$mod$17$and$710^{4n}=1$mod$17$. – Tsemo Aristide Jul 1 '18 at 22:57 • I can get more on board with this – Prime Jul 1 '18 at 22:59 Once you have$710^{447} \equiv 4^{149}\equiv 4^{2(74)}\times 4$, note that$4^2 \equiv -1 \pmod {17}$Your work is fine except that you lost a factor of 4 after "So,". You went from considering$4^{149}$in the previous paragraph to considering$4^{148}$in the rest of your work. As you note in your scratchwork,$n^a\times n^b = n^{a+b}$and$(n^{a})^{b} \equiv n^{ab}$Hint: Since$4^2 = 16 \equiv -1\pmod {17}$Then$4^{2(74)} \equiv (4^{2})^{74}\equiv (-1)^{74}\$

• Can you elaborate on this? – Prime Jul 1 '18 at 22:54
• Ah. I imagined it was a silly algebra mistake. – Prime Jul 1 '18 at 22:56