معادله ی همنهشتی

ash1374 · 1391/5/23

فرض کنید

$m,n,p$

سه عدد طبیعی دلخواه هستند. ثابت کنید

$m^{x}+x\equiv p(mod(n))$

در مجموعه ی اعداد طبیعی جواب دارد.

Aref · 1391/5/24

پاسخ : معادله ی همنهشتی

ash1374 گفت

استقرا می زنیم.

پایه ی استقرا(

$n=1$

): دو طرف به پیمانه ی

$1$

صفر هستند. پس معادله ی داده شده در مجموعه ی اعداد طبیعی جواب دارد.

فرض کنید معادله ی داده شده برای هر

$k<n$

جواب دارد.

فرض کنید

$(n,\varphi(n))=d$

و داشته باشیم:

$m^x+x\equiv t \pmod n$

.

$x\leadsto x+k\varphi (n)$

نتیجه می دهد که معادله ی

$m^y+y\equiv t+dk \pmod n$

جواب طبیعی دارد.
اکنون طبق فرض استقرا معادله ی

$m^z+z\equiv t \pmod d$

جواب دارد. پس

$m^z+z= t +dl\Rightarrow m^z+z\equiv t+dl \pmod n$

.

$\square$

EDIT:
این 1000 امین پست من ه.:4: