11
$\begingroup$

I am doing this problem mentioned above and I know the answer because I know Euler's Theorem that $$a^{\varphi{(m)}}\equiv{1}\pmod{m}.$$ I used 100 as my modulus and got that the last two digits of $7^{355}$ are $43$.

My question is this. What prime should I pick to solve this problem using Fermat's theorem $$a^{p-1}\equiv{1}\pmod{p}$$ As a precursor problem, the author (Dudley; Elementary Number Theory) asked to find the last digit of the number above; so using a modulus $5$, $7^4\equiv{1}\pmod{5}$ by Fermat. Since the answer is $7^{355}\equiv{3}\pmod{5}$, the last digit is either $3$ or $8$. Since $7$ is odd, the answer will clearly be odd, so $3$ is it. The book is working linearly, building from the previous chapters and Euler's Theorem isn't mentioned for another two chapters (I remembered Euler from a problem solving class in college).

So again, what prime would be best? How should I procede?

EDIT: I've seen a bunch of problems on the site and none that I looked at did it using Fermat. If there is one, that could be posted and I would be happy.

EDIT 2: it seems that the problem of finding of finding the last two digits using is rather difficult because of the implication that we need something mod 100. Is there a way around this , like adding a step or complexifying, in order to finish the problem with Fermat?

$\endgroup$
9
$\begingroup$

Repeated Squaring

If Euler wasn't mentioned I would consider it a problem about repeated squaring: $$ \begin{align} 7^2&\equiv 49\\ 7^4&\equiv 49^2\equiv 1\\ 7^8&\equiv 1^2\equiv 1\\ 7^{(2^n)}&\equiv 1\mbox{ for }n>1 \end{align} $$ Now $355=101100011_2=2^8+2^6+2^5+2^1+2^0$ and so accordingly $$ \large \begin{align} 7^{355}&=7^{2^8+2^6+2^5+2^1+2^0}\\ &\equiv7^{2^1+2^0}\\ &=343\\ &\equiv 43 \end{align} $$

Chinese Remainder Approach

Knowing the Chinese Remainder Theorem then simplifies the size of the calculations since modulo 25 we have $7^2\equiv -1$ and $7^{4k}\equiv 1$ and therefore $7^{355}\equiv 7^3\equiv -7$ modulo 25.

At the same time we have $7^2\equiv 1$ modulo 4 so that $7^{355}\equiv 7\equiv 3$ modulo 4. Now $25\equiv 1$ modulo 4 and $-24\equiv 1$ modulo 25 so $$ 7^{355}\equiv 3\cdot 25-7\cdot (-24) $$ modulo 100 due to the Chinese Remainder Theorem. Finishing this calculation we get $$ 3\cdot 25-7\cdot(-24)=10\cdot 25-7=243 $$ to see that $7^{355}\equiv 243\equiv 43$ modulo 100.

$\endgroup$
  • 2
    $\begingroup$ Perhaps one might jump to the conclusion that the powers of all integers modulo 100 do not repeat in a manner that can be calculated by hand. However, it should be mentioned that 7 is a special case, together with a few other integers. Good answer! $\endgroup$ – Yiyuan Lee Jan 11 '14 at 0:45
  • $\begingroup$ @String I think $355=101100011_2=2^9+2^7+2^6+2^1+2^0$ should be replaced by $355=101100011_2=2^8+2^6+2^5+2^1+2^0$. $\endgroup$ – learner May 17 '14 at 3:44
  • $\begingroup$ @learner: You are quite right about that! $\endgroup$ – String Jun 18 '14 at 13:29
5
$\begingroup$

Use the primes 2 and 5 and combine the results using the chinese remainder theorem to get the last digit.

$\endgroup$
  • 1
    $\begingroup$ I need the last two digits... I got the last digit as 3 using fermat with $p=5$. $\endgroup$ – Eleven-Eleven Jan 10 '14 at 23:29
  • $\begingroup$ Yeah, that was the question...I'm using Dudley's Elementary Number Theory and the chapter is dedicated to Fermat and Wilson ($(p-1)!\equiv{-1}\pmod{p}$)...I don't think Wilson applies here... $\endgroup$ – Eleven-Eleven Jan 10 '14 at 23:32
  • $\begingroup$ why use 11 in particular? How to deduce that? $\endgroup$ – Eleven-Eleven Jan 10 '14 at 23:55
  • 1
    $\begingroup$ Just noticed that it does not work, sorry. $\endgroup$ – Peter Jan 10 '14 at 23:55
  • 2
    $\begingroup$ There must be some additional trick because the remainder with respect to any prime has nothing to do with the remainder with respect to 100. $\endgroup$ – Peter Jan 11 '14 at 0:17
4
$\begingroup$

Hint $\rm\ mod\ 100\!:\ \color{#c00}{7^4} \overset{\,}\equiv (50-1)^2 \equiv \color{#c00}1\ $ so $\rm\ 7^N = 7^{\,4J+K}\!\equiv (\color{#c00}{7^4})^J 7^K\equiv \color{#c00}1^J7^K\!\equiv 7^K$

Said equivalently $\rm\ 7^{\large\color{#0a0}4}\equiv 1\, \Rightarrow\, 7^{\large N}\equiv 7^{\large K}\ (mod\ 100)\ $ if $\rm\ K\,\equiv\, N\ \ (mod\ \color{#0a0}4).\,$ To make arithmetic simple, choose the smallest such $\rm\,K > 0,\ $ namely $\rm\ \: K \,= (N\ \,mod\,\ \color{#0a0}4).\,$ See also this answer.

$\endgroup$
  • $\begingroup$ right, but I'm looking for a solution using Fermat, which requires the modulus to be prime. $\endgroup$ – Eleven-Eleven Jan 10 '14 at 23:42
  • 3
    $\begingroup$ @Chris It is a bit unnatural to try to deduce that $\,7^4 \equiv 1\pmod{100}$ using only little Fermat. Why force that limitation on yourself? Unless that was explicitly specified in the book, I suspect you are misjudging what was intended. Doing it as above requires only grade school arithmetic $7^4 = (-1+50)^2 = 1 -2(50)+50^2\equiv 1\pmod{100}$ $\endgroup$ – Bill Dubuque Jan 10 '14 at 23:54
  • 3
    $\begingroup$ Mainly because I think there is a way, and I like the challenge...in so many words! As I mentioned in the problem, I already know how to solve the problem, I was just trying to use Fermat since it seems possible... $\endgroup$ – Eleven-Eleven Jan 10 '14 at 23:56
  • $\begingroup$ Fermat's "Little Theorem" is a special case of $a^{\psi (b)}\equiv 1 \pmod b$ when $a b\neq 0$ and $\gcd (a,b)=1.$ $\endgroup$ – DanielWainfleet May 13 '16 at 16:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.