Remainder
- Thread starter Lottasv
- Start date
pka
Elite Member
- Joined
- Jan 29, 2005
- Messages
- 11,989
Look at this calculation. The mod function gives the remainder when one integer is divided by another.
What you want to do is find a power of 3 such that \(\displaystyle 3^k \pmod{7} = 1\)
The existence of \(\displaystyle k\) is assured as 3 and 7 have no common factors.
A bit of pencil pushing shows \(\displaystyle 3^6 \pmod{7} = 1\)
\(\displaystyle 177 = 29\cdot 6 + 3\\
3^{177} = 3^{29\cdot 6 + 3} = \\
\left(3^6\right)^{29}\cdot 3^3\)
\(\displaystyle 3^{177} \pmod{7} = \left(3^6\right)^{29}\cdot 3^3 \pmod{7} = \\
\left(3^6 \pmod{7}\right)^{29} \cdot 3^3 \pmod{7} = \\
1^{29} \cdot \left(27 \pmod{7}\right) = 6\)
The existence of \(\displaystyle k\) is assured as 3 and 7 have no common factors.
A bit of pencil pushing shows \(\displaystyle 3^6 \pmod{7} = 1\)
\(\displaystyle 177 = 29\cdot 6 + 3\\
3^{177} = 3^{29\cdot 6 + 3} = \\
\left(3^6\right)^{29}\cdot 3^3\)
\(\displaystyle 3^{177} \pmod{7} = \left(3^6\right)^{29}\cdot 3^3 \pmod{7} = \\
\left(3^6 \pmod{7}\right)^{29} \cdot 3^3 \pmod{7} = \\
1^{29} \cdot \left(27 \pmod{7}\right) = 6\)
Steven G
Elite Member
- Joined
- Dec 30, 2014
- Messages
- 14,598
Is googling really going to help even if you got the answer? You need to think about this.
Although you should do this yourself I will tell you the thought process.
1) You should not just know the remainder when 3^177 is divided by 7.
2) 3(no power) will have a 0 remainder when divided by 7 since 7 does not go into 3*3*3...*3
3) But what about 1? Can 3(some power) have a remainder of 1 when divided by 7? If yes this will be helpful. If 3n has a remainder of 1 when by 7, then we can play this game- 3177 = (3n)b* 3c and the remainder of dividing 3177 by 7 will be the same remainder when dividing 3c by 7. Note that nb+c=177 and 0<c<7