5

How do I solve this?

Prove that ${ ({ 3299 }^{ 5 }+6) }^{ 18 }\equiv 1\pmod{112}$

Also, it would be very helpful if you could give me something to read on the topic since this is not taught at my school and this area of mathematics seems interesting to me.

Thomas Andrews
  • 177,126
  • 1
    There are two important tools to solve this: the Chinese remainder theorem and Euler's theorem. Google will help you more than I can do in comments. – Arthur Apr 08 '16 at 14:33
  • 1
    Hint; Prove it $\pmod {16}$ and $\pmod{7}$ and then use that $112=16\cdot 7$. – Thomas Andrews Apr 08 '16 at 14:33

2 Answers2

2

$$3299=51\pmod{112}=3\cdot17\pmod{112=\color{purple}{2^4\cdot7}}$$

So we get:

$$\color{red}{\text{modulo}\;\, 16\;\;\text{all the time}}:\;3299=3\cdot1=3\implies 3299^5=3^4\cdot3=1\cdot3=3\implies$$

$$(3299^5+6)^{18}=(3+6)^{18}=\left(9^2\right)^91^9=1$$

and now

$$\color{green}{\text{modulo}\;\;7\;\;\text{all the time}}: 3299=2\implies2^5=4\implies (3299^5+6)^{18}=$$

$$=(4-1)^{18}=3^{18}=(3^3)^6=(-1)^6=1$$

So there.

DonAntonio
  • 211,718
  • 17
  • 136
  • 287
0

You can take advantage of the following properties of congruences:

If $a \equiv b\ (\textrm{mod}\ m)$ and $c \equiv d\ (\textrm{mod}\ m)$, then:

$a+c \equiv b+d\ (\textrm{mod}\ m)$

$a^n \equiv b^n\ (\textrm{mod}\ m)$

and the fact that congruences are transitive. So, step 1 would be to calculate the value of $x$:

$3299 \equiv x\ (\textrm{mod}\ 112)$

Once you've calculated $x$:

$3299^5 \equiv x^5\ (\textrm{mod}\ 112)$

and

$3299^5 + 6 \equiv x^5 + 6\ (\textrm{mod}\ 112)$

Then, if you can show that

$(x^5 + 6)^{18} \equiv 1\ (\textrm{mod}\ 112)$

the transitive property of congruences can be used to prove that

$3299^5 + 6 \equiv 1\ (\textrm{mod}\ 112)$

The problem with this approach is that $(x^5 + 6)^{18}$ is a huge number. But, if you use the transitive property in certain portions of the calculation, you can simplify the calculations. For example, I calculated $x = 51$ in the first step. Since $51^5 + 6 \equiv 73 \ (\textrm{mod}\ 112)$, you can raise $73$ to the $18$th power instead of $x^5 + 6$. You would also need to break the $73^{18}$ into multiple computations as well.

Any textbook on elementary number theory would be a good place to start researching this. I've been reading a textbook written by Kenneth Rosen called "Elementary Number Theory and its applications".

ashleydc
  • 159
  • This does not work. ${ 3299 }^{ 5 }+6≡1\quad (mod\quad 112)$ is not true. I think the mistake is in assuming that if ${ { (3299 }^{ 5 }+6) }^{ 18 }≡1\quad (mod\quad112)$ then ${ { 3299 }^{ 5 }+6 }≡1\quad (mod\quad112)$. Anyways, thank you for your book reccomendation. –  Apr 08 '16 at 16:37
  • @David - yes I see my mistake now. I've edited my answer. The approach will still work, but I think it is not a very efficient approach to the problem (at least not for this equation). – ashleydc Apr 08 '16 at 17:23