سوالی در مورد همنهشتی ها $x^2\equiv x\quad mod(p_1\cdots p_n)$

Question

اگر $p_n,...,p_2,p_1$ اعداد اول متمایزی باشند نشان دهید که معادله $$x^2\equiv x\quad mod(p_1\cdots p_n)$$ که در ان $0\leq x< p_1\cdots p_n$ درست $2^n$ جواب دارد.

ممنون میشم اینو به طور کامل توضیح بدین. یی میگفت با حلقه ها هم حل می شود.

Comments

کسی نیست جواب بده ایا؟؟؟؟

---

کسی نبود جواب بده؟؟
یکیتوون کمک کنید

---

لطفا صبور باشید اگر کسی بتونه جواب میده. متاسفانه در تخصص من نیست. ولی اون چیزی که الان به ذهنم میرسه اینه که به صورت $x(x-1)\equiv 0\ mod(p_1...p_n)$ بنویسیم. و  دراینصورت $x(x-1)\equiv 0 \ mod(p_i)$ برای هر $i$ . و لذا $x\equiv 0\ mod(p_i)$ و $x\equiv 1\ mod(p_i)$ برای هر $i$ . حالا باید از قضیه باقیمانده چینی https://en.wikipedia.org/wiki/Chinese_remainder_theorem استفاده کنیم. به احتمال زیاد به خاطر اینکه $x\equiv 0\ mod(p_i)$ و $x\equiv 1\ mod(p_i)$ ها دو حالت دارند و با بقیه معادلات همنهشتی تشکیل دستگاه $n$ تایی می دهند و هرکدام طبق قضیه چینی دارای یک جواب هستند پس در کل $2^n$ جواب داریم.
در مورد اینکه با حلقه ها هم حل میشه در اون لینک عبارتی مثل این آورده
 $\frac{\mathbb Z}{n\mathbb Z}\cong \frac{\mathbb Z}{p_1\mathbb Z}\times \frac{\mathbb Z}{p_n\mathbb Z}$ ممکنه شما بتونید ازش استفاده کنید.

---

fardina@  خیلی ممنون از جوابتون.اونجایی که گفتین ((به خاطر اینکه x≡0 mod(pi) و x≡1 mod(pi) ها دو حالت دارند )) کدوم دو حالت؟؟میشه بیشتر توضیح بدین

---

@clover
من خیلی مطمئن نیستم شاید بحث دقیقتری لازم داره ولی من مثلا گفتم (شاید) برای دستگاه
$\begin{cases}x\equiv 0 mod(p_1)\\ \vdots \\ x\equiv 0 mod(p_n)\end{cases}$ طبق قضیه چینی یک جواب داریم. بعد برای دستگاه
$\begin{cases}x\equiv 1 mod(p_1)\\ x\equiv 0 mod(p_2)\\ \vdots \\ x\equiv 0 mod(p_n)\end{cases}$
یک جواب داریم و به همین ترتیب بقیه دستگاههای هم نهشتی رو در نظر بگیریم کلا $2^n$ دستگاه میشن. البته قضیه چینی نمیگه که جواب منحصربه فرده بلکه میگه حتما جواب داره ولی شرط $0
\leq x< p_1\cdots p_n$
شاید نتیجه بده که جواب منحصر به فرد خواهد بود!
امیدوارم کسی بتونه بیشتر راهنمایی کنه.

Answer 1

Comments

در مورد صورت کلی جواب ها خللی اساسی وجود دارد که به آن توجه نکردم. این جواب ها باید به پیمانه حاصلضرب نخستین n عدد اول تبدیل شود و در کل صورت جواب ها هم از نظر تعداد و هم از نظر مقدار اشتباه است. پس من فقط تعداد کل جواب ها را به دست آورده و درستی آن را ثابت کرده ام.