Mathcenter Forum  

Go Back   Mathcenter Forum > คณิตศาสตร์โอลิมปิก และอุดมศึกษา > ทฤษฎีจำนวน
สมัครสมาชิก คู่มือการใช้ รายชื่อสมาชิก ปฏิทิน ค้นหา ข้อความวันนี้ ทำเครื่องหมายอ่านทุกห้องแล้ว

ตั้งหัวข้อใหม่ Reply
 
เครื่องมือของหัวข้อ ค้นหาในหัวข้อนี้
  #1  
Old 25 ตุลาคม 2013, 23:53
coke's Avatar
coke coke ไม่อยู่ในระบบ
ลมปราณบริสุทธิ์
 
วันที่สมัครสมาชิก: 30 ตุลาคม 2011
ข้อความ: 101
coke is on a distinguished road
Default ช่วยข้อเกี่ยวกับการหารลงตัวหน่อยครับ

$จงพิสูจน์ว่า \frac{2^{n-1}+1}{n} ไม่เป็นจํานวนเต็มทุกจํานวนเต็มบวก n$

รบกวนช่วยทําหน่อยค้าบบ ขอบคุณล่วงหน้าครับ
__________________
~การรู้ว่าตนเองไม่รู้ เป็นการก้าวไกลไปสู่ความรู้ ~
คนฉลาดเรียนรู้ข้อผิดพลาดของคนอื่น แต่คนโง่เรียนรู้ข้อผิดพลาดของตนเอง
ตอบพร้อมอ้างอิงข้อความนี้
  #2  
Old 28 กรกฎาคม 2020, 20:17
Anton's Avatar
Anton Anton ไม่อยู่ในระบบ
เริ่มฝึกวรยุทธ์
 
วันที่สมัครสมาชิก: 27 กรกฎาคม 2020
ข้อความ: 20
Anton is on a distinguished road
Send a message via ICQ to Anton Send a message via AIM to Anton Send a message via MSN to Anton Send a message via Yahoo to Anton Send a message via Skype™ to Anton
Default

อ้างอิง:
Problem. Find all positive integers $n$ such that the expression
$$\frac{2^{n-1}+1}{n}$$
is an integer.
We claim that the only positive integer $n$ such that $\dfrac{2^{n-1}+1}{n}$ is an integer is $n=1$. Suppose on the contrary that there exists a positive integer $n>1$ such that $n\mid 2^{n-1}+1$.

Note that $n$ must be odd. If $p$ is any prime integer that divides $n$, then
$$\left(2^{\frac{n-1}{2}}\right)^2=2^{n-1}\equiv -1\pmod{p}\,.$$
Thus, $-1$ is a quadratic residue modulo $p$. Consequently, $p\equiv 1\pmod{4}$. This shows that $n\equiv 1\pmod{4}$.

We shall now prove that every prime natural number $p$ that divides $n$ must satisfy $p\equiv 1\pmod{2^m}$ for every positive integer $m$. The cases $k=1$ and $k=2$ have been established. We suppose that the claim is true for $m=k$, where $k\geq 2$ is an integer. Then, $n\equiv 1\pmod{2^k}$, whence
$$\left(2^{\frac{n-1}{2^k}}\right)^{2^k}=2^{n-1}\equiv -1\pmod{p}$$
for any prime natural number $p$ that divides $n$. We already know that $p\equiv 1\pmod{2^k}$. We need to show that $p\equiv 1\pmod{2^{k+1}}$.

Let $g$ be a generator of the multiplicative group $(\mathbb{Z}/p\mathbb{Z})^\times$. Then, $-1\equiv g^s\pmod{p}$ for some integer $s$. Since $p\equiv 1\pmod{2^k}$ and $-1$ is a $(2^k)$-th power modulo $p$, we see that $2^k\mid s$. If $p\not\equiv1\pmod{2^{k+1}}$, then $\dfrac{p-1}{2^k}$ is an odd integer, and so
$$-1=(-1)^{\frac{p-1}{2^k}}\equiv (g^s)^{\frac{p-1}{2^k}}=g^{(p-1)\,\frac{s}{2^k}}\pmod{p}\,.$$
Since $\dfrac{s}{2^k}$ is an integer and $g^{p-1}\equiv 1\pmod{p}$ by Fermat's Little Theorem, we obtain
$$-1\equiv \big(g^{p-1}\big)^{\frac{s}{2^k}}\equiv 1\pmod{p}\,,$$
which is a blatant contradiction. Therefore, $p\equiv 1\pmod{2^{k+1}}$ must hold.

From the result above, we arrive at a contradiction. This is because, for any prime natural number $p$, $p-1$ can be divided by $2$ only finitely many times. Therefore, $n=1$ is the only positive integer such that $n$ divides $2^{n-1}+1$.
__________________
Потом доказывай, что ты не верблюд.

28 กรกฎาคม 2020 21:27 : ข้อความนี้ถูกแก้ไขแล้ว 3 ครั้ง, ครั้งล่าสุดโดยคุณ Anton
ตอบพร้อมอ้างอิงข้อความนี้
ตั้งหัวข้อใหม่ Reply


เครื่องมือของหัวข้อ ค้นหาในหัวข้อนี้
ค้นหาในหัวข้อนี้:

ค้นหาขั้นสูง

กฎการส่งข้อความ
คุณ ไม่สามารถ ตั้งหัวข้อใหม่ได้
คุณ ไม่สามารถ ตอบหัวข้อได้
คุณ ไม่สามารถ แนบไฟล์และเอกสารได้
คุณ ไม่สามารถ แก้ไขข้อความของคุณเองได้

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
ทางลัดสู่ห้อง


เวลาที่แสดงทั้งหมด เป็นเวลาที่ประเทศไทย (GMT +7) ขณะนี้เป็นเวลา 06:46


Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Modified by Jetsada Karnpracha