1

I guess I should start by saying that $4\equiv 11\mod 7$, but I don't know how to proceed from here.

Is it possible to do without using Fermat's theorem?

Thank you.

user126638
  • 79
  • 1
    You got $4$ different solutions for your question. Hope this makes you happy ! – lsp Feb 12 '14 at 16:43
  • @lsp at least every answer reach the same 4. – LeeNeverGup Feb 12 '14 at 17:06
  • P.S. Direct way : $4^{451}=33810849992682575766549746234657062817206228866311777416189485377707129763630391006362704376810060025259161279568456235448470243808171874384034494621628132922136747775936325386798817131291292227393550906125516057865473810736099951285657401521090334495330469177455231893504 = 4 + 7 \cdot 4830121427526082252364249462093866116743746980901682488027069339672447109090055858051814910972865717894165897081208033635495749115453124912004927803089733274590963967990903626685545304470184603913364415160788008266496258676585707326522485931584333499332924168207890270500$ – LeeNeverGup Feb 12 '14 at 17:08
  • @LeeNeverGup, how did you manage to do it? – Indrayudh Roy Feb 12 '14 at 17:48
  • @IndrayudhRoy There is a nice program named pari/gp, which does such kind of calculations. – LeeNeverGup Feb 12 '14 at 20:05

5 Answers5

3

As $\displaystyle4=2^2,4^{451}=(2^2)^{451}=2^{902}$

Now, $\displaystyle2^3=8\equiv1\pmod7$ and $902\equiv2\pmod3$

$\displaystyle\implies2^{902}=(2^3)^{300}\cdot2^2\equiv1^{300}\cdot2^2\pmod7$

lab bhattacharjee
  • 274,582
1

$$4^{451}=2^{902}=4(2^{900})=4(7+1)^{300}$$ From binomial expansion, we can say that $7$ leaves a remainder of $1$ when it divides $(7+1)^{300}$.Hence: $$4(7+1)^{300}=4(7k+1)=7l+4$$ So you can conclude that $r=4$.

lsp
  • 4,745
1

Note $(4^0, 4^1, 4^2, 4^3) \mod 7 \equiv (1,4,16,64) \mod 7 \equiv (1,4,2,1)$ so there is a cycle of 3. Now $4^{451} = 4 \cdot 4^{3 \cdot 150}$ so you will make $150$ cycles from $1$ and come back to $4$. The remainder should be $4$.

gt6989b
  • 54,422
1

Hint $\ {\rm mod}\ 7\!:\ 2^{\large 3}\equiv 1\,\Rightarrow\, 2^{\large 2(\color{#c00}{451})}\!\equiv 2^{\large \color{}2},\,$ by $\,{\rm mod}\ 3\!:\ \color{#c00}{451}\equiv 4\!+\!5\!+\!1\equiv \color{#c00}1,\,$ by $\,10\equiv 1.$

Bill Dubuque
  • 272,048
1

You can do this way too,

$4 \ \equiv -3 \ (mod \ 7)$

$4^2 \ \equiv \ 9$

$4^2 \ \equiv \ 2$

$4^6 \ \equiv \ 8$

$4^6 \ \equiv \ 1$

$4^{450} \ \equiv \ 1$

$4^{451} \ \equiv 4 \ (mod \ 7)$

If we can find congruent to $ \pm 1$ then the problem becomes easier.

UPDATE:

You can also do

$4^3 \ \equiv \ 1 \ (mod \ 7) $

$4^{450} \ \equiv \ 1 $

$4^{451} \ \equiv \ 4 \ (mod \ 7) $

neofoxmulder
  • 1,166