13
$\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$
1

3 Answers 3

Reset to default
13
$\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$
3
  • 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, 2014 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, 2014 at 3:44
  • $\begingroup$ @learner: You are quite right about that! $\endgroup$
    – String
    Jun 18, 2014 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$
7
  • 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, 2014 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, 2014 at 23:32
  • $\begingroup$ why use 11 in particular? How to deduce that? $\endgroup$
    – Eleven-Eleven
    Jan 10, 2014 at 23:55
  • 1
    $\begingroup$ Just noticed that it does not work, sorry. $\endgroup$
    – Peter
    Jan 10, 2014 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, 2014 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$
4
  • $\begingroup$ right, but I'm looking for a solution using Fermat, which requires the modulus to be prime. $\endgroup$
    – Eleven-Eleven
    Jan 10, 2014 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, 2014 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, 2014 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, 2016 at 16:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .