Derive the following congruence....

  • Thread starter Thread starter Math100
  • Start date Start date
  • Tags Tags
    Derive
AI Thread Summary
The discussion focuses on deriving the congruence a^21 ≡ a (mod 15) using Fermat's theorem. It demonstrates that a^3 ≡ a (mod 3) and a^5 ≡ a (mod 5), leading to the conclusion that a^21 ≡ a (mod 15). The participants also explore alternative expressions for the congruence, emphasizing clarity in the proof. Some confusion arises regarding specific congruences, but it is acknowledged as a minor issue. Overall, the proof is affirmed as valid and the discussion highlights the importance of understanding modular arithmetic.
Math100
Messages
816
Reaction score
229
Homework Statement
Derive the following congruence:
## a^{21}\equiv a\pmod {15} ## for all ## a ##.
[Hint: By Fermat's theorem, ## a^{5}\equiv a\pmod {5} ##.]
Relevant Equations
None.
Proof:

Observe that ## 15=3\cdot 5 ##.
Applying the Fermat's theorem produces:
## a^{3}\equiv a\pmod {3} ## and ## a^{5}\equiv a\pmod {5} ##.
Thus
\begin{align*}
&(a^{3})^{7}\equiv a^{7}\pmod {3}\implies a^{21}\equiv [(a^{3})^{2}\cdot a]\pmod {3}\implies a^{21}\equiv a\pmod {3}\\
&(a^{5})^{4}\equiv a^{4}\pmod {5}\implies a^{20}\equiv a^{4}\pmod {5}\implies a^{21}\equiv a\pmod {5}.\\
\end{align*}
Therefore, ## a^{21}\equiv a\pmod {15} ## for all ## a ##.
 
Physics news on Phys.org
Maybe you should write ##a^{21}\equiv a^7\equiv a^3\cdot a^3 \cdot a\equiv a\cdot a\cdot a\equiv a^3\equiv a\pmod{3}.## Or at least ##(a^3)^2\cdot a\equiv a^2\cdot a\equiv a^3\equiv a\pmod{3}.##

I stumbled upon ##a^6\cdot a\equiv a\pmod{3}## which was not immediately clear (to me).

But again: might be due to local time. :cool:
 
fresh_42 said:
Maybe you should write ##a^{21}\equiv a^7\equiv a^3\cdot a^3 \cdot a\equiv a\cdot a\cdot a\equiv a^3\equiv a\pmod{3}.## Or at least ##(a^3)^2\cdot a\equiv a^2\cdot a\equiv a^3\equiv a\pmod{3}.##

I stumbled upon ##a^6\cdot a\equiv a\pmod{3}## which was not immediately clear (to me).

But again: might be due to local time.
Sorry, it's my fault.
 
Math100 said:
Sorry, it's my fault.
Not at all. I'm just a little bit slow at night time. That's not your fault. It only proves that the Earth is not flat.
 
Since ##px^9+q## is the factor, then ##x^9=\frac{-q}{p}## will be one of the roots. Let ##f(x)=27x^{18}+bx^9+70##, then: $$27\left(\frac{-q}{p}\right)^2+b\left(\frac{-q}{p}\right)+70=0$$ $$b=27 \frac{q}{p}+70 \frac{p}{q}$$ $$b=\frac{27q^2+70p^2}{pq}$$ From this expression, it looks like there is no greatest value of ##b## because increasing the value of ##p## and ##q## will also increase the value of ##b##. How to find the greatest value of ##b##? Thanks
Back
Top