ЁЭЬЩ (ЁЭЬЩ (p * q)) рдХреА рдЧрдгрдирд╛ рдХрд░рдиреЗ рдХрд╛ рдПрдХ рдХреБрд╢рд▓ рддрд░реАрдХрд╛ рдЬрд╣рд╛рдВ p рдФрд░ q рдкреНрд░рдзрд╛рди рд╣реИрдВ
рд▓рд╢реНрдХрд░ $p$ рддрдерд╛ $q$ рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛ рдФрд░ $\phi$рдпреВрд▓рд░ рдХрд╛ рдХреБрд▓ рдХрд╛рд░реНрдпред рдХреНрдпрд╛ рдХрдВрдкреНрдпреВрдЯрд┐рдВрдЧ рдХрд╛ рдПрдХ рдХреБрд╢рд▓ рддрд░реАрдХрд╛ рд╣реИ$\phi(\phi(p\cdot q)) = \phi((p-1)(q-1))$, рдХрд┐ рдмрд╕ рдлреИрдХреНрдЯрд░рд┐рдВрдЧ рдкрд░ рдЖрдзрд╛рд░рд┐рдд рдирд╣реАрдВ рд╣реИ $p-1$ рддрдерд╛ $q-1$?
рдЬрд╛рд╣рд┐рд░ рд╣реИ, рдЕрдЧрд░ $p$ рддрдерд╛ $q$ рджреЛ рдмрд░рд╛рдмрд░ рдирд╣реАрдВ, $p-1$ рддрдерд╛ $q-1$ рд╕рдорд╛рди рд░реВрдк рд╕реЗ рдФрд░ рдЗрд╕рдХреЗ рдлрд▓рд╕реНрд╡рд░реВрдк рдЙрдирдХрд╛ рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдб рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдб рд╕реЗ рдкреВрд░реА рддрд░рд╣ рднрд┐рдиреНрди рд╣реИ $p$ рддрдерд╛ $q$ред рдЗрд╕рд▓рд┐рдП рдореИрдВ рдорд╛рдирддрд╛ рд╣реВрдВ рдХрд┐ рдРрд╕рд╛ рдХреЛрдИ рд╢реЙрд░реНрдЯрдХрдЯ рдореМрдЬреВрдж рдирд╣реАрдВ рд╣реИред
рдХреНрдпрд╛ рдореИрдВ рдХреБрдЫ рдЕрдирджреЗрдЦреА рдХрд░рддрд╛ рд╣реВрдВ?
рдЬрд╡рд╛рдм
рдирд╣реАрдВ, рдХреБрд╢рд▓рддрд╛ рд╕реЗ рдирд╣реАрдВ, рд╕рд╛рдорд╛рдиреНрдп рд░реВрдк рд╕реЗ рдирд╣реАрдВред рдорд╛рди рд▓реАрдЬрд┐рдП$p=2p'+1$ рддрдерд╛ $q=2q'+1$ рдХрд╣рд╛рдБ рдкреЗ $p',q'$рдкреНрд░рд╛рдЗрдо рд╣реИрдВред рдлрд┐рд░ рдлреИрдХреНрдЯрд░рд┐рдВрдЧ$pq$рдорд╛рдирд╛ рдЬрд╛рддрд╛ рд╣реИ рдХрд┐ рдпрд╣ рдХрдард┐рди рд╣реИред (рд╡рд╛рд╕реНрддрд╡ рдореЗрдВ, рдЗрди рдЕрдкрд░рд╛рдзреЛрдВ рдХреЛ рд╕реБрд░рдХреНрд╖рд┐рдд рдЕрдкрд░рд╛рдзреЛрдВ рдХреЗ рд░реВрдк рдореЗрдВ рдЬрд╛рдирд╛ рдЬрд╛рддрд╛ рд╣реИ , рдФрд░ рджреЛ рд╕реБрд░рдХреНрд╖рд┐рдд рдЕрдкрд░рд╛рдзреЛрдВ рдХреЗ рдЙрддреНрдкрд╛рдж рдХреЛ рдлреИрдХреНрдЯ рдХрд░рдирд╛ рдХрдард┐рди рдорд╛рдирд╛ рдЬрд╛рддрд╛ рд╣реИред)
$$\varphi(\varphi(pq))=\varphi(4p'q')=2\varphi(p')\varphi(q')=2(p'-1)(q'-1).$$
рдпрджрд┐ рдЖрдк рдЧрдгрдирд╛ рдХрд░ рд╕рдХрддреЗ рд╣реИрдВ $\varphi(\varphi(pq))$ рд╕реЗ $pq$ рдХреБрд╢рд▓рддрд╛ рд╕реЗ $p,q$ рдЗрд╕ рд░реВрдк рдореЗрдВ, рддрдм рдЖрдк рдХрд╛рд░рдХ рдмрди рд╕рдХрддреЗ рд╣реИрдВ $pq$ рдХреБрд╢рд▓рддрд╛ рд╕реЗ $p,q$рдЗрд╕ рд░реВрдк рдореЗрдВред рдХрдЯреМрддреА рдирд┐рдореНрдирд╛рдиреБрд╕рд╛рд░ рдХрд╛рдо рдХрд░рддреА рд╣реИред рджреНрд╡рд┐рдШрд╛рдд рдХрд╛рд░реНрдп рдкрд░ рд╡рд┐рдЪрд╛рд░ рдХрд░реЗрдВ$f$ рдХреЗ рджреНрд╡рд╛рд░рд╛ рджрд┐рдпрд╛ рдЧрдпрд╛
$$f(x)=(x-p')(x-q')=x^2 -(p'+q') + p'q'.$$
рд╣рдо рдХреЗ рдЧреБрдгрд╛рдВрдХ рдХреА рдЧрдгрдирд╛ рдХрд░ рд╕рдХрддреЗ рд╣реИрдВ $f$, рдЬреИрд╕рд╛
$$p'+q'=[pq-2\varphi(\varphi(pq))+3]/4$$ $$p'q'=[pq+2\varphi(\varphi(pq))-5]/8$$
рддреЛ рдЖрдк рдХреА рдЬрдбрд╝реЛрдВ рдХреЛ рд╣рд▓ рдХрд░рдиреЗ рдХреЗ рд▓рд┐рдП рджреНрд╡рд┐рдШрд╛рдд рд╕реВрддреНрд░ рдХрд╛ рдЙрдкрдпреЛрдЧ рдХрд░ рд╕рдХрддреЗ рд╣реИрдВ $f$ рдФрд░ рдареАрдХ рд╣реЛ рдЬрд╛рдУ $p',q'$ред рдЗрд╕рд╕реЗ рдХрд╛ рдХрд╛рд░рдХрддреНрд╡$pq$ рдмрд░рд╛рдордж рдХрд┐рдпрд╛ рдЬрд╛ рд╕рдХрддрд╛ рд╣реИред
рддреЛ, рдирд╣реАрдВ, рдЖрдк рдХреБрдЫ рднреА рдЕрдирджреЗрдЦреА рдирд╣реАрдВ рдХрд░ рд░рд╣реЗ рд╣реИрдВред рдЧрдгрдирд╛ рдХрд░рдиреЗ рдХреЗ рд▓рд┐рдП рдХреЛрдИ рдХреБрд╢рд▓ рддрд░реАрдХрд╛ рдирд╣реАрдВ рд╣реИ$\varphi(\varphi(pq))$ рдордирдорд╛рдиреА рд╕рдВрдЦреНрдпрд╛ рдХреЗ рд▓рд┐рдП $pq$ (рдЬрдм рддрдХ рдлреИрдХреНрдЯрд░рд┐рдВрдЧ рдЖрд╕рд╛рди рди рд╣реЛ)ред