KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

ELTE

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

A. 415. Let a>b and n be arbitrary positive integers. Prove that n divides \varphi(an-bn).

(Proposed by Balázs Strenner, Budapest)

(5 points)

Deadline expired on 15 January 2007.


Solution. Let d=gcd(a,b), p=a/d and q=b/d. Since pn-qn divides an-bn, \varphi(pn-qn) divides \varphi(an-bn) and it is sufficient to prove n|\varphi(pn-qn). Therefore, it can be assumed that a and b are co-prime.

Note that a and b are relatively prime with an-bn as well.

Consider the multiplicative group of the reduced residue system modulo an-bn. Let c=ab-1. Since

bn<bnc=abn-1<bnc2=a2bn-2<...<bncn-1=an-1b<bncn=an=bn+(an-bn),

the order of element c is exactly n.

By Lagrange's theorem, the order of element c divides the order of the group, therefore n divides \varphi(an-bn).


Statistics on problem A. 415.
9 students sent a solution.
5 points:Gyenizse Gergő, Hujter Bálint, Kisfaludi-Bak Sándor, Kónya 495 Gábor, Korándi Dániel, Lovász László Miklós, Nagy 224 Csaba, Nagy 235 János, Tomon István.


  • Problems in Mathematics of KöMaL, December 2006

  • Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley