ماراتن نظریه ی اعداد (سطح پیشرفته)

aras2213 · 1394/3/30

پاسخ : ماراتن نظریه ی اعداد (سطح پیشرفته)

برای هر عدد اول و دلخواه مثل q داریم:

$f(x+q)\equiv qf'(x)+f(x) \textrm{ }(mod \textrm{ }q^2)$

اگر درجه f بیشتر از 1 باشه اون وقت مقادیری که مشتق اون به ازای اعداد طبیعی میگیره بینهایت عامل اول دارن.چون درجه مشتقش حداقل 1 میشه.مثلا فرض کنید :

$q\mid f'(x_0)$

$q\mid f'(x_0)\rightarrow f(x_0+q)\equiv qf'(x_0)+f(x_0)\equiv f(x_0) \textrm{ }(mod \textrm{ }q^2)$

این یعنی

$f(x_0+q)\equiv f(x_0) \textrm{ }(mod \textrm{ }q^2)$

و همچنین

$x_0+q, x_0$

به پیمانه q^2 همنهشت نیستند.حالا نشون میدیم که این شرط سوال رو نقض میکنه.
اگر

$a=q^2$

و b بین 1 تا q^2 تغییر کنه،نتیجه میشه که

$f(x)$

به ازای

$x=1,2,...,q^2$

همه باقیمانده های ممکن رو به پیمانه q^2 میده.یعنی:

$i\not\equiv j\textrm{ }(mod\textrm{ }q^2)\rightarrow f(i)\not\equiv f(j)\textrm{ }(mod\textrm{ }q^2)$

اما برای

$x_0+q, x_0$

چنین چیزی برقرار نیست.پس درجه f حداکثر 1 هه.این جا به بعدش هم زیاد سخت نیست.درسته؟

---- دو نوشته به هم متصل شده است ----

Dadgarnia گفت

http://artofproblemsolving.com/community/c5h1083472p4774020

Dadgarnia · 1394/3/31

پاسخ : ماراتن نظریه ی اعداد (سطح پیشرفته)

aras2213 گفت

برای هر عدد اول و دلخواه مثل q داریم:

$f(x+q)\equiv qf'(x)+f(x) \textrm{ }(mod \textrm{ }q^2)$

اگر درجه f بیشتر از 1 باشه اون وقت مقادیری که مشتق اون به ازای اعداد طبیعی میگیره بینهایت عامل اول دارن.چون درجه مشتقش حداقل 1 میشه.مثلا فرض کنید :

$q\mid f'(x_0)$

$q\mid f'(x_0)\rightarrow f(x_0+q)\equiv qf'(x_0)+f(x_0)\equiv f(x_0) \textrm{ }(mod \textrm{ }q^2)$

این یعنی

$f(x_0+q)\equiv f(x_0) \textrm{ }(mod \textrm{ }q^2)$

و همچنین

$x_0+q, x_0$

به پیمانه q^2 همنهشت نیستند.حالا نشون میدیم که این شرط سوال رو نقض میکنه.
اگر

$a=q^2$

و b بین 1 تا q^2 تغییر کنه،نتیجه میشه که

$f(x)$

به ازای

$x=1,2,...,q^2$

همه باقیمانده های ممکن رو به پیمانه q^2 میده.یعنی:

$i\not\equiv j\textrm{ }(mod\textrm{ }q^2)\rightarrow f(i)\not\equiv f(j)\textrm{ }(mod\textrm{ }q^2)$

اما برای

$x_0+q, x_0$

چنین چیزی برقرار نیست.پس درجه f حداکثر 1 هه.این جا به بعدش هم زیاد سخت نیست.درسته؟

---- دو نوشته به هم متصل شده است ----

Community - Art of Problem Solving

به نظر من كه درسته. لطفا سوال بعد رو هم بذار.

aras2213 · 1394/3/31

پاسخ : ماراتن نظریه ی اعداد (سطح پیشرفته)

همه اعداد طبیعی a,b رو پیدا کنید که

$a^3+6ab+1,b^3+6ab+1$

هر دو مکعب کامل باشند.

Dadgarnia · 1394/3/31

پاسخ : ماراتن نظریه ی اعداد (سطح پیشرفته)

aras2213 گفت

فرض مي كنيم

$a^3+6ab+1\geq (a+2)^3,b^3+6ab+1\geq (b+2)^3$

با جمع اين دو نامساوي بدست مياد:

$6a^2+6b^2+12a+12b+14\leq 12ab\leq 6a^2+6b^2$

كه تناقضه پس حداقل يكي از اين دو نامساوي غلطه. فرض مي كنيم

$a^3+6ab+1<(a+2)^3$

پس داريم:

$a^3+6ab+1=(a+1)^3\Rightarrow a=2b-1$

$\Rightarrow b^3+6ab+1=b^3+12b^2-6b+1$

از طرفي براي

$b>11$

داريم

$(b+3)^3<b^3+12b^2-6b+1<(b+4)^3$

پس كافيه حالات خاص رو بررسي كنيم كه ديگه كاري نداره.

---- دو نوشته به هم متصل شده است ----

سوال بعد:
همه اعداد اول

$p,q,r$

را بيابيد به طوريكه

$p|q^r+1,q|r^p+1,r|p^q+1$

.

TheOverlord · 1394/3/31

پاسخ : ماراتن نظریه ی اعداد (سطح پیشرفته)

Dadgarnia گفت

ابتدا فرض كنيد هر سه عدد فردند.
دقت كنيد كه اين اعداد بديهتا دو به دو نسبت به هم اول، و نتيجتا متمايزند.
حال واضح است كه

$ord^p_r=2 \ or \ 2q, ord^r_q=2\ or\ 2p,ord^q_p=2 \ or \ 2r$

حال اگر هر سه عدد دو نباشد، بنابر تقارن

$ord^p_r=2q$

آنگاه اگر

$ord^r_q=2$

آنگاه داريم

$ord^p_r=2q\Rightarrow 2q|r-1\Rightarrow q|r-1, ord^r_q=2\Rightarrow q\not |r-1$

كه تناقض است. بنابرين

$ord^r_q=2p$

و به طريق مشابه

$ord^q_p=2r$

پس اگر بزرگترين عدد از بين اين ٣ بنا به تقارن

$p$

باشد چون

$ord^r_q=2p\Rightarrow 2p|q-1\Rightarrow p<q$

كه تناقض است. بنابرين هر سه مرتبه برابر دو هستند.
پس

$p|r+1,r|q+1,q|p+1$

اما اين اعداد فرد هستند، پس اگر بزرگترينشان

$p$

باشد دوباره بخاطر

$p|\frac{r+1}{2}$

به تناقض ميرسيم.
پس يكي از اين اعداد اول فرد نيست پس ٢ است. بنا به تقارن

$p=2$

حال بديهتا باقي اعداد فردند.دقت كنيد كه

$ord^2_r=2 \ or \ 2q, ord^r_q=4$

حال اگر

$ord^2_r=2$

بديهتا

$r=3,q=5$

پس در اين حالت مساله حل است. اما اگر

$ord^2_r=2q\Rightarrow q|r-1,ord^r_q=4\Rightarrow q|r^2+1\Rightarrow q|1^2+1\Rightarrow q=2$

كه تناقض است. پس. تنها جوابها همان

$(2,5,3),(3,2,5),(5,3,2)$

هستند.
سوال بعد: فرض كنيد جمع مقسوم عليه هاي عدد

$n$

برابر

$\sigma (n)$

باشد. ثابت كنيد براي يك عدد طبيعي ثابت مثل

$a$

بينهايت عدد طبيعي

$m$

وجود دارند كه در خاصيت

$\sigma(am)<\sigma(am+1)$

صدق كنند.

Dadgarnia · 1394/4/1

پاسخ : ماراتن نظریه ی اعداد (سطح پیشرفته)

TheOverlord گفت

ابتدا فرض كنيد هر سه عدد فردند.
دقت كنيد كه اين اعداد بديهتا دو به دو نسبت به هم اول، و نتيجتا متمايزند.
حال واضح است كه

$ord^p_r=2 \ or \ 2q, ord^r_q=2\ or\ 2p,ord^q_p=2 \ or \ 2r$

حال اگر هر سه عدد دو نباشد، بنابر تقارن

$ord^p_r=2q$

آنگاه اگر

$ord^r_q=2$

آنگاه داريم

كه تناقض است. بنابرين

$ord^r_q=2p$

و به طريق مشابه

$ord^q_p=2r$

پس اگر بزرگترين عدد از بين اين ٣ بنا به تقارن

$p$

باشد چون

$ord^r_q=2p\Rightarrow 2p|q-1\Rightarrow p<q$

كه تناقض است. بنابرين هر سه مرتبه برابر دو هستند.
پس

$p|r+1,r|q+1,q|p+1$

اما اين اعداد فرد هستند، پس اگر بزرگترينشان

$p$

باشد دوباره بخاطر

$p|\frac{r+1}{2}$

به تناقض ميرسيم.
پس يكي از اين اعداد اول فرد نيست پس ٢ است. بنا به تقارن

$p=2$

حال بديهتا باقي اعداد فردند.دقت كنيد كه

$ord^2_r=2 \ or \ 2q, ord^r_q=4$

حال اگر

$ord^2_r=2$

بديهتا

$r=5,q=13$

پس در اين حالت مساله حل است. اما اگر

$ord^2_r=2q\Rightarrow q|r-1,ord^r_q=4\Rightarrow q|r^2+1\Rightarrow q|1^2+1\Rightarrow q=2$

كه تناقض است. پس. تنها جوابها همان

$(2,13,5),(5,2,13),(13,5,2)$

هستند.
سوال بعد: فرض كنيد جمع مقسوم عليه هاي عدد

$n$

برابر

$\sigma (n)$

باشد. ثابت كنيد براي يك عدد طبيعي ثابت مثل

$a$

بينهايت عدد طبيعي

$m$

وجود دارند كه در خاصيت

$\sigma(am)<\sigma(am+1)$

صدق كنند.

وقتي كه

$q|r-1$

بديهتا

$q|r^2-1$

شما چه جوري نتيجه گرفتيد كه

$q|r+1$

؟ در ضمن هر دو حالت

$ord_q^r=2$

و

$ord_p^q=2$

بايد بررسي بشن و توي آخر راه حل هم يه اشتباه كوچيك كردين جواباش

$(2,5,3)$

و جايگشت هاي دوريش هستند.

TheOverlord · 1394/4/1

پاسخ : ماراتن نظریه ی اعداد (سطح پیشرفته)

Dadgarnia گفت

از اونجا كه مرتبه برابر دو هست، پس برابر يك نيست، پس

$q\not |r-1$

ويرايش كردم تا درست شه.

ثابت كردم از

$ord^p_r=2q,ord^r_q=2$

به تناقض ميرسيم. به طريق مشابه از

$ord^r_q=2p,ord^q_p=2$

هم به تناقض ميرسيم.
جواب آخر رو هم ويرايش كردم.

aras2213 · 1394/4/4

پاسخ : ماراتن نظریه ی اعداد (سطح پیشرفته)

TheOverlord گفت

فرض کنید

$q$

کوچکترین عدد اول بزرگتر از

$\sigma (a)$

باشه و

$p_1< p_2< ...< p_t$

به ترتیب کوچکترین اعداد اول بزرگتر از

$q$

باشن به طوری که

$\frac{1}{p_1}+...+\frac{1}{p_t}> q$

که چون جمع معکوس اعداد اول نامتناهی است، t وجود دارد.طبق باقیمانده چینی r وجود داره که

$ar+1\equiv q\textrm{ }(mod\textrm{ }q^2),ar+1\equiv 0\textrm{ }(mod\textrm{ }p_1...p_t)$

حالا تصاعد

$q^2p_1...p_t\times k+r$

بینهایت عدد اول داره(طبق دیریشله)فرض کنید m یکی از این اعداد اول باشه که از a بزرگتر باشه.

در این صورت:

$\sigma (am)=(m+1)\sigma (a),\sigma (am+1)=(q+1)(\sigma (\frac{am+1}{q}))$

.
همچنین:

$(q+1)(\sigma (\frac{am+1}{q}))> \sigma (a)\times ((1+\frac{1}{p_1}+...+\frac{1}{p_t})(\frac{am+1}{q}))$

.پس:

پس هر یک از این m ها یه جواب برای سواله.

nima-1376 · 1394/4/4

پاسخ : ماراتن نظریه ی اعداد (سطح پیشرفته)

نشان دهید بینهایت عدد طبیعی

$n$

هست که

$n^{2}+1$

خالی از مربع باشد.

Dadgarnia · 1394/4/5

پاسخ : ماراتن نظریه ی اعداد (سطح پیشرفته)

nima-1376 گفت

من قبلا اينو توي همين ماراتن گذاشتم. لطفا سوالو عوض كنيد.

nima-1376 · 1394/4/6

پاسخ : ماراتن نظریه ی اعداد (سطح پیشرفته)

سوال اول : نشان دهید بی نهایت

$x\neq y$

هست که

$x^{2}+y^{3}\mid x^{3}+y^{2}$

سوال دوم: فرض کنید

$k\geq 2$

عددی طبیعی است. نشان دهید بیشمار عدد طبیعی

$n$

هست به طوری که

$n\mid 1^{n}+2^{n}+...+k^{n}$

سوال سوم :100 عدد طبیعی متمایز داریم زیر هر کدام ب.م.م 99 تای دیگر را مینویسیم. حداکثر چند تا از این اعداد متمایزند؟

سوال چهارم: نشان دهید تعداد اعداد اولی که میتوان عدد دلخواه

$A$

را در بین ارقام آن به صورت متوالی یافت نامتناهی است!

Dadgarnia · 1394/4/6

پاسخ : ماراتن نظریه ی اعداد (سطح پیشرفته)

nima-1376 گفت

١- قرار بدين

$x=k^6-k^3-k,y=k^5-k^2-1$

.
٢- اگه

$k$

زوج باشه

$k+1$

حداقل يه عامل اول و فرد مثل

$p$

داره حالا بنابر لم دو خط براي

$1\leq x\leq \frac{k}{2}$

و

$\ell$

دلخواه داريم:

$p^{\ell}|x^{p^{\ell}}+(k-x+1)^{p^{\ell}}\Rightarrow p^{\ell}|\sum_{i=1}^k i^{p^{\ell}}$

اگه

$k$

فرد باشه

$k$

حداقل يه عامل اول و فرد مثل

$p$

داره حالا بنابر لم دو خط براي

$1\leq x\leq \frac{k-1}{2}$

و

$\ell$

دلخواه داريم:

$p^{\ell}|x^{p^{\ell}}+(k-x)^{p^{\ell}},p^{\ell}|k^{p^{\ell}}\Rightarrow p^{\ell}|\sum_{i=1}^ki^{p^{\ell}}$

---- دو نوشته به هم متصل شده است ----

٣-

$p_1,p_2,\cdots,p_{100}$

اعدادي اول و متمايز هستند قرار بدين

$a_k=\frac{\prod_{i=1}^{100}p_i}{p_k}$

در اينصورت زير

$a_k$

،

$p_k$

رو بايد بنويسيم و بديهتا همه ي اعداد با هم متمايزند. درسته؟

Dadgarnia · 1394/4/24

پاسخ : ماراتن نظریه ی اعداد (سطح پیشرفته)

nima-1376 گفت

لطفا يكي جواب اينو بذاره :|

MNikdan · 1394/4/24

پاسخ : ماراتن نظریه ی اعداد (سطح پیشرفته)

Dadgarnia گفت

طبق قضیه ی دیریکله میدونیم که اگه

$gcd(a,b)=1$

اون وقت به ازای بی نهایت

$x$

عدد

$ax+b$

اول خواهد بود.
فرض میکنیم

$N$

تعداد ارقام

$A$

باشه. حالا کافیه قرار بدیم

$a=10^{N+1}$

و

$b=10A+1$

ُ . واضحه که

$gcd(a,b)=1$

پس طبق دیریکله بی نهایت عدد اول به صورت

$10^{N+1}x+10A+1$

داریم که توی همه ی این اعداد عدد

$A$

به طور کامل دیده میشه...

Dadgarnia · 1394/4/24

پاسخ : ماراتن نظریه ی اعداد (سطح پیشرفته)

MNikdan گفت

احتمالا منظور ايشون راه حل مقدماتي بوده چون وبلاگ بچه هاي 26 هم يه بار اين سوالو گذاشته بودن و گفته بودن راه حل مقدماتي داره.

---- دو نوشته به هم متصل شده است ----

حالا شما يه سوال بذارين تا به ماراتن ادامه بديم.

MNikdan · 1394/4/24

پاسخ : ماراتن نظریه ی اعداد (سطح پیشرفته)

آخه اسم تاپیک ماراتن پیشرفته بود. منم فکر کردم مشکلی نداره... هر چند که دیریکله خیلی هم پیشرفته نیست !!!
به هر حال :
1) ثابت کنید بی نهایت

$n$

وجود داره که تمام عوامل اول

$n^2+1$

از

$n$

کوچکتر باشن.

2)فرض کنید

$P(n)$

برابر حاصل ضرب عوامل اول متمایز

$n$

باشه. دنباله

$a(n)$

از اعداد طبیعی بزرگتر از 1 به صورت زیر تعریف میشه:

$a(n+1)=a(n)+P(a(n))$

که

$a(1)$

دلخواهه. ثابت کنید به ازای هر

$k$

دنباله ای حسابی به طول

$k$

از جمله های متوالی این دنباله وجود داره.

Dadgarnia · 1394/4/24

پاسخ : ماراتن نظریه ی اعداد (سطح پیشرفته)

MNikdan گفت

من منظورم نظریه اعداد مقدماتی بود نه مقدماتی و پیشرفته ای که اینجا تعریف شده.
1) کافیه ثابت کنیم معادله

$n^2-2m^2=-1$

بی نهایت جواب طبیعی داره. این معادله ی پله و چون یه جواب نابدیهی مثل

$n=41,m=29$

داره بی نهایت جواب براش وجود داره.

Dadgarnia · 1394/8/10

پاسخ : ماراتن نظریه ی اعداد (سطح پیشرفته)

سوال بعد:
ثابت کنید اعداد صحیح

$a,b,c,d$

که قدر مطلق همه بزرگتر از ۱۰۰۰۰۰۰ است وجود دارند كه

$\frac{1}{a}+\frac{1}{b}+\frac{1}{c}+\frac{1}{d}=\frac{1}{abcd}$

.

Seyed Amir Hosseini · 1394/8/11

پاسخ : ماراتن نظریه ی اعداد (سطح پیشرفته)

Dadgarnia گفت

$\frac{\sum abc}{abcd} = \frac{1}{abcd} \Rightarrow \sum abc = 1$

اينطوري ميشه! مطمينيد سوال درسته؟

Dadgarnia · 1394/8/11

پاسخ : ماراتن نظریه ی اعداد (سطح پیشرفته)

Seyed Amir Hosseini گفت

ببخشيد منظورم قدر مطلقشون بود.

ماراتن نظریه ی اعداد (سطح پیشرفته)

New Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member

Active Member

New Member