0
$\begingroup$

I was given a how problem set with the following problems to solve (I'm allowed to use a calculator for all operations excluding exponentiation):

$3^{23} + 3 ≡ 5^{37} − 4 \pmod 7$

$1,000,001^{999,999} ≡ 1 \pmod {1, 000, 000}$

...I know Fermat's Little Theorem should help me manipulate even these vast numbers, but I don't know where or how to begin. For the second one, should I start with a much smaller number, like $1,000,001 ≡ 1 \pmod {1,000,000}$? (That should hold, right?)

$\endgroup$
  • $\begingroup$ You should begin with Fermat's little theorem in the case of $3^{23}$ and the prime $p=7$. What does it tell you ? $\endgroup$ – Dietrich Burde Jul 7 '16 at 14:59
  • $\begingroup$ For the second one, what you stated is true. Now, if you raise both sides to any power... $\endgroup$ – Some Math Student Jul 7 '16 at 15:00
  • $\begingroup$ Alternatively, use the binomial theorem to unfold $(1+10^6)^{999999}$. All but the first term are multiples of $10^6$. $\endgroup$ – Henning Makholm Jul 7 '16 at 15:02
1
$\begingroup$

You should learn some basic rules for congruences before you proceed with Fermat's Theorem.

Firstly,

  • Congruences with same modulo n are- $1.$Reflexive,$2.$Symmetric and $3.$ Transitive.

This simply means congruences with same modulo can be added,subtracted and multiplied to give new congruences.

For eg, $2^2\equiv1\pmod3$ and $4^2\equiv1\pmod3$.

This implies,

1.$2^2+4^2\equiv(1+1)\pmod3$

2.$2^2\times2^2\equiv(1\times1)\pmod3$

Similarly they can also be subtracted.

See,from them product rule of congruences,we see that if $a\equiv b\pmod c$ then,$a^n\equiv b^n\pmod c$.

So,if $1000001\equiv1\pmod{1000000}$ then $1000001^n\equiv1^n\pmod{1000000}$.For your question,$n=999,999$.

Hint for your second first part-

$3^{7-1}\equiv1\pmod7$ (By,Fermat's Little Theorem)

$\implies3^{23}\equiv3^5\pmod7$

$\implies3^{23}\equiv5\pmod7$

Also, we see,$3\equiv{-4}\pmod7$

Adding the congruences,$3^{23}+3\equiv5+(-4)\pmod7$.

Now,try to find out why the $5^{37}$.

$\endgroup$
1
$\begingroup$

Hint: Modulo 7, $$3^{23}\equiv3^{21}3^{2}\equiv(3^{7})^{3}3^{2}\equiv3^{3}3^{2}\equiv3\cdot3^{2}3^{2}\equiv3\cdot2\cdot2\equiv-1\cdot2\equiv-2\equiv5.$$ You should be able to use similar manipulations on these types of problems.

$\endgroup$
0
$\begingroup$

$$\begin{align} & {{3}^{6}}\overset{7}{\mathop{\equiv }}\,1\,\,\,\Rightarrow \,\,\,{{3}^{18}}\overset{7}{\mathop{\equiv }}\,1\,\,\,\Rightarrow \,\,\,{{3}^{23}}\overset{7}{\mathop{\equiv }}\,243\,\,\Rightarrow {{3}^{23}}+3\overset{7}{\mathop{\equiv }}\,246\,\overset{7}{\mathop{\equiv }}\,1 \\ & {{5}^{6}}\overset{7}{\mathop{\equiv }}\,1\,\,\,\Rightarrow \,\,\,{{5}^{36}}\overset{7}{\mathop{\equiv }}\,1\,\,\,\Rightarrow \,\,\,{{5}^{37}}\overset{7}{\mathop{\equiv }}\,5\,\,\Rightarrow {{5}^{37}}-4\overset{7}{\mathop{\equiv }}\,1\,\,\,\,\,\,\, \\ \end{align}$$ then $${{3}^{23}}+3\overset{7}{\mathop{\equiv }}\,{{5}^{37}}-4$$ $${{({{10}^{6}}+1)}^{999999}}=\sum\limits_{i=0}^{999999}{\left( \begin{matrix} 999999 \\ i \\ \end{matrix} \right)}{{({{10}^{6}})}^{999999-i}}\,\overset{{{10}^{6}}}{\mathop{\equiv }}\,1\,\,\,\,$$

$\endgroup$
  • $\begingroup$ Isn't your method too complex? $\endgroup$ – tatan Jul 7 '16 at 15:05

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.