# Derive ## a^{7}\equiv a\pmod {42} ## for all ## a ##

• Math100
In summary: Keep up the good work!In summary, applying Fermat's theorem in its general version of ##a^p\equiv a\pmod{p}##, we can prove that ##a^{7}\equiv a\pmod {42}## for all ##a##, even without using the specific version of ##\operatorname{gcd}(a,p)=1##. This is a more general and efficient approach to proving this congruence.
Math100
Homework Statement
Derive the following congruence:
## a^{7}\equiv a\pmod {42} ## for all ## a ##.
Relevant Equations
None.
Proof:

Observe that ## 42=6\cdot 7=2\cdot 3\cdot 7 ##.
Applying the Fermat's theorem produces:
## a\equiv 1\pmod {2}, a^{2}\equiv 1\pmod {3} ## and ## a^{6}\equiv 1\pmod {7} ##.
Thus
\begin{align*}
&a\equiv 1\pmod {2}\implies a^{6}\equiv 1\pmod {2}\implies a^{7}\equiv a\pmod {2}\\
&a^{2}\equiv 1\pmod {3}\implies a^{6}\equiv 1\pmod {3}\implies a^{7}\equiv a\pmod {3}\\
&a^{6}\equiv 1\pmod {7}\implies a^{7}\equiv a\pmod {7}.\\
\end{align*}
Therefore, ## a^{7}\equiv a\pmod {42} ## for all ## a ##.

Fermat's theorem doesn't apply to all ##a##.

Then what should we apply here without the Fermat's theorem?

Math100 said:
Then what should we apply here without the Fermat's theorem?
You have used Fermat's theorem in the version ##\operatorname{gcd}(a,p)=1.##
The general version says ##a^p\equiv a\pmod{p}.## Try that one.

Proof:

Observe that ## 42=6\cdot 7=2\cdot 3\cdot 7 ##.
Applying the Fermat's theorem produces:
## a^{2}\equiv a\pmod {2}, a^{3}\equiv a\pmod {3} ## and ## a^{7}\equiv a\pmod {7} ##.
Thus
\begin{align*}
&a^{2}\equiv a\pmod {2}\implies a^{6}\equiv a^{3}\pmod {2}\\
&\implies a^{7}\equiv a^{4}\pmod {2}\implies a^{7}\equiv (a^{2}\cdot a^{2})\pmod {2}\implies a^{7}\equiv a\pmod {2}\\
&a^{3}\equiv a\pmod {3}\implies a^{6}\equiv a^{2}\pmod {3}\\
&\implies a^{7}\equiv a^{3}\pmod {3}\implies a^{7}\equiv a\pmod {3}.\\
\end{align*}
Since ## 2, 3, 7 ## are relatively prime to each other,
it follows that ## a^{7}\equiv a\pmod {2\cdot 3\cdot 7}\implies a^{7}\equiv a\pmod {42} ##.
Therefore, ## a^{7}\equiv a\pmod {42} ## for all ## a ##.

Right. I would write the congruences in one line, e.g.
##a^3\equiv a \pmod{3}\Longrightarrow a^7\equiv a^3\cdot a^3 \cdot a\equiv a\cdot a \cdot a \equiv a^3\equiv a\pmod{3}.##

Last edited:
Math100
fresh_42 said:
Right. I would write the congruences in one line, e.g.
##a^3\equiv a \pmod{3}\Longrightarrow a^7\equiv a^3\cdot a^3 \cdot a\equiv a\cdot a \cdot a \equiv a^3\equiv a\pmod{3}.##
This is way better.

Last edited by a moderator:

## 1. What does "Derive ## a^{7}\equiv a\pmod {42} ## for all ## a ##" mean?

This statement means that for any integer value of ## a ##, when raised to the seventh power and divided by 42, the remainder will always be equal to ## a ##.

## 2. How can this be proven?

This can be proven using modular arithmetic, specifically the rules of congruence. By manipulating the equation and substituting different values for ## a ##, it can be shown that the statement holds true for all integer values of ## a ##.

## 3. What are the practical applications of this statement?

This statement has practical applications in cryptography and coding theory. It can also be used in simplifying mathematical calculations involving large numbers.

## 4. Can this statement be extended to other exponents?

Yes, this statement can be extended to any positive integer exponent. For example, "Derive ## a^{11}\equiv a\pmod {42} ## for all ## a ##" would also hold true.

## 5. Are there any exceptions to this statement?

No, there are no exceptions to this statement. It holds true for all integer values of ## a ##.

### Similar threads

• Precalculus Mathematics Homework Help
Replies
7
Views
2K
• Precalculus Mathematics Homework Help
Replies
2
Views
1K
• Precalculus Mathematics Homework Help
Replies
19
Views
1K
• Precalculus Mathematics Homework Help
Replies
4
Views
1K
• Precalculus Mathematics Homework Help
Replies
1
Views
988
• Precalculus Mathematics Homework Help
Replies
3
Views
846
• Precalculus Mathematics Homework Help
Replies
3
Views
908
• Precalculus Mathematics Homework Help
Replies
4
Views
1K
• Precalculus Mathematics Homework Help
Replies
2
Views
960
• Precalculus Mathematics Homework Help
Replies
6
Views
849