Hello,
I am trying to to proof that :
if gcd(a,n)=1 then a^Phi (n) = 1 (mod n)
and I found the following as a proof, but I cannot understand what happened from ((X)) to ((Y))
(how can we get [FONT=MathJax_Math-italic]c[/FONT][FONT=MathJax_Math-italic]a[FONT=MathJax_Math-italic]i[/FONT][/FONT][FONT=MathJax_Main]≡[/FONT][FONT=MathJax_Math-italic]c[/FONT][FONT=MathJax_Math-italic]a[FONT=MathJax_Math-italic]j[/FONT][/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]mod[/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main]) from [/FONT][FONT=MathJax_Math-italic]c[/FONT][FONT=MathJax_Math-italic]a[FONT=MathJax_Math-italic]i[/FONT][/FONT][FONT=MathJax_Main]≡[/FONT][FONT=MathJax_Math-italic]a[FONT=MathJax_Math-italic]j[/FONT][/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]mod[/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main]) )
[/FONT]
The proof:
Consider the set of all numbers less than [FONT=MathJax_Math-italic]n and relatively prime to it. Let [FONT=MathJax_Main]{[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Math-italic]φ[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main]}[/FONT] be this set.[/FONT]
Consider a number [FONT=MathJax_Math-italic]c[FONT=MathJax_Main]<[/FONT][FONT=MathJax_Math-italic]n[/FONT] and relatively prime to it i.e. [FONT=MathJax_Math-italic]c[/FONT][FONT=MathJax_Main]∈[/FONT][FONT=MathJax_Main]{[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main]…[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Math-italic]φ[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main]}[/FONT]
[/FONT]
First observe that for any [FONT=MathJax_Math-italic]a[FONT=MathJax_Math-italic]i[/FONT]: [FONT=MathJax_Math-italic]c[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Math-italic]i[/FONT][FONT=MathJax_Main]≡[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Math-italic]j[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]mod[/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main])[/FONT]for somej. ((X)) (True since [FONT=MathJax_Math-italic]c[/FONT] and [FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Math-italic]i[/FONT] are themselves relatively prime to n [FONT=MathJax_Math-italic]nn.[/FONT][/FONT]
If [FONT=MathJax_Math-italic]c[FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Math-italic]i[/FONT][FONT=MathJax_Main]≡[/FONT][FONT=MathJax_Math-italic]c[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Math-italic]j[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]mod[/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main])[/FONT]((Y)) then [FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Math-italic]i[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Math-italic]j[/FONT] (True as cancellation can be done since [FONT=MathJax_Math-italic]c[/FONT]c is relatively prime to[FONT=MathJax_Math-italic]n[/FONT]n).[/FONT]
Hence, if we now consider the set [FONT=MathJax_Main]{[FONT=MathJax_Math-italic]c[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Math-italic]c[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Math-italic]c[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Math-italic]φ[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main]}[/FONT] this is just a permutation of the set [FONT=MathJax_Main]{[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Math-italic]φ[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main]}[/FONT].[/FONT]
Thereby, we have [FONT=MathJax_Size2]∏[FONT=MathJax_Math-italic]k[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Math-italic]φ[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Math-italic]c[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Math-italic]k[/FONT][FONT=MathJax_Main]≡[/FONT][FONT=MathJax_Size2]∏[/FONT][FONT=MathJax_Math-italic]k[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Math-italic]φ[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Math-italic]k[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]mod[/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main])[/FONT]
[/FONT]
Hence, we get [FONT=MathJax_Math-italic]c[FONT=MathJax_Math-italic]φ[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Size2]∏[/FONT][FONT=MathJax_Math-italic]k[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Math-italic]φ[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Math-italic]k[/FONT][FONT=MathJax_Main]≡[/FONT][FONT=MathJax_Size2]∏[/FONT][FONT=MathJax_Math-italic]k[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Math-italic]φ[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Math-italic]k[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]mod[/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main])[/FONT].[/FONT]
Now, note that [FONT=MathJax_Size2]∏[FONT=MathJax_Math-italic]k[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Math-italic]φ[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Math-italic]k[/FONT] is relatively prime to [FONT=MathJax_Math-italic]n[/FONT] and hence you can cancel them on both sides to get[/FONT]
I am trying to to proof that :
if gcd(a,n)=1 then a^Phi (n) = 1 (mod n)
and I found the following as a proof, but I cannot understand what happened from ((X)) to ((Y))
(how can we get [FONT=MathJax_Math-italic]c[/FONT][FONT=MathJax_Math-italic]a[FONT=MathJax_Math-italic]i[/FONT][/FONT][FONT=MathJax_Main]≡[/FONT][FONT=MathJax_Math-italic]c[/FONT][FONT=MathJax_Math-italic]a[FONT=MathJax_Math-italic]j[/FONT][/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]mod[/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main]) from [/FONT][FONT=MathJax_Math-italic]c[/FONT][FONT=MathJax_Math-italic]a[FONT=MathJax_Math-italic]i[/FONT][/FONT][FONT=MathJax_Main]≡[/FONT][FONT=MathJax_Math-italic]a[FONT=MathJax_Math-italic]j[/FONT][/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]mod[/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main]) )
[/FONT]
The proof:
Consider the set of all numbers less than [FONT=MathJax_Math-italic]n and relatively prime to it. Let [FONT=MathJax_Main]{[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Math-italic]φ[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main]}[/FONT] be this set.[/FONT]
Consider a number [FONT=MathJax_Math-italic]c[FONT=MathJax_Main]<[/FONT][FONT=MathJax_Math-italic]n[/FONT] and relatively prime to it i.e. [FONT=MathJax_Math-italic]c[/FONT][FONT=MathJax_Main]∈[/FONT][FONT=MathJax_Main]{[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main]…[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Math-italic]φ[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main]}[/FONT]
[/FONT]
First observe that for any [FONT=MathJax_Math-italic]a[FONT=MathJax_Math-italic]i[/FONT]: [FONT=MathJax_Math-italic]c[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Math-italic]i[/FONT][FONT=MathJax_Main]≡[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Math-italic]j[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]mod[/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main])[/FONT]for somej. ((X)) (True since [FONT=MathJax_Math-italic]c[/FONT] and [FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Math-italic]i[/FONT] are themselves relatively prime to n [FONT=MathJax_Math-italic]nn.[/FONT][/FONT]
If [FONT=MathJax_Math-italic]c[FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Math-italic]i[/FONT][FONT=MathJax_Main]≡[/FONT][FONT=MathJax_Math-italic]c[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Math-italic]j[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]mod[/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main])[/FONT]((Y)) then [FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Math-italic]i[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Math-italic]j[/FONT] (True as cancellation can be done since [FONT=MathJax_Math-italic]c[/FONT]c is relatively prime to[FONT=MathJax_Math-italic]n[/FONT]n).[/FONT]
Hence, if we now consider the set [FONT=MathJax_Main]{[FONT=MathJax_Math-italic]c[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Math-italic]c[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Math-italic]c[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Math-italic]φ[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main]}[/FONT] this is just a permutation of the set [FONT=MathJax_Main]{[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Math-italic]φ[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main]}[/FONT].[/FONT]
Thereby, we have [FONT=MathJax_Size2]∏[FONT=MathJax_Math-italic]k[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Math-italic]φ[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Math-italic]c[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Math-italic]k[/FONT][FONT=MathJax_Main]≡[/FONT][FONT=MathJax_Size2]∏[/FONT][FONT=MathJax_Math-italic]k[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Math-italic]φ[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Math-italic]k[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]mod[/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main])[/FONT]
[/FONT]
Hence, we get [FONT=MathJax_Math-italic]c[FONT=MathJax_Math-italic]φ[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Size2]∏[/FONT][FONT=MathJax_Math-italic]k[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Math-italic]φ[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Math-italic]k[/FONT][FONT=MathJax_Main]≡[/FONT][FONT=MathJax_Size2]∏[/FONT][FONT=MathJax_Math-italic]k[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Math-italic]φ[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Math-italic]k[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]mod[/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main])[/FONT].[/FONT]
Now, note that [FONT=MathJax_Size2]∏[FONT=MathJax_Math-italic]k[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Math-italic]φ[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Math-italic]a[/FONT][FONT=MathJax_Math-italic]k[/FONT] is relatively prime to [FONT=MathJax_Math-italic]n[/FONT] and hence you can cancel them on both sides to get[/FONT]
[FONT=MathJax_Math-italic]c[/FONT][FONT=MathJax_Math-italic]φ[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main]≡[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]mod[/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main])[/FONT]
whenever [FONT=MathJax_Main]([/FONT][FONT=MathJax_Math-italic]c[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Math-italic]c[/FONT][FONT=MathJax_Math-italic]a[FONT=MathJax_Math-italic]i[/FONT][/FONT][FONT=MathJax_Main]≡[/FONT][FONT=MathJax_Math-italic]a[FONT=MathJax_Math-italic]j[/FONT][/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]mod[/FONT][FONT=MathJax_Math-italic]n[/FONT][FONT=MathJax_Main])[/FONT]