版塊導(dǎo)航: 正在加載中...

登錄注冊

應(yīng)《網(wǎng)絡(luò)安全法》要求，自2017年10月1日起，未進(jìn)行實名認(rèn)證將不得使用互聯(lián)網(wǎng)跟帖服務(wù)。為保障您的帳號能夠正常使用，請盡快對帳號進(jìn)行手機(jī)號驗證，感謝您的理解與支持！

24小時熱門版塊排行榜

返回列表

375291258

鐵桿木蟲 (著名寫手)

應(yīng)助: 1 (幼兒園)
金幣: 11067.5
散金: 33
帖子: 2982
在線: 74.1小時
蟲號: 1858830
注冊: 2012-06-14
性別: GG
專業(yè): 組合數(shù)學(xué)

[求助] the existence of a common primitive root 已有1人參與

If p and q are distinct primes, then the existence of a common primitive root of p and q.
這個結(jié)論如何證明。

回復(fù)此樓

» 猜你喜歡

一志愿中國海洋大學(xué)，生物學(xué)，301分，求調(diào)劑已經(jīng)有6人回復(fù)
081700化工學(xué)碩調(diào)劑已經(jīng)有3人回復(fù)
材料學(xué)碩318求調(diào)劑已經(jīng)有4人回復(fù)
329求調(diào)劑已經(jīng)有4人回復(fù)
一志愿吉林大學(xué)材料學(xué)碩321求調(diào)劑已經(jīng)有11人回復(fù)
一志愿蘇州大學(xué)材料求調(diào)劑，總分315（英一）已經(jīng)有3人回復(fù)
0703化學(xué)調(diào)劑已經(jīng)有14人回復(fù)
320求調(diào)劑0856 已經(jīng)有3人回復(fù)
307求調(diào)劑已經(jīng)有9人回復(fù)
288求調(diào)劑已經(jīng)有15人回復(fù)

1樓 2014-10-13 06:07:18

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

Edstrayer

版主 (著名寫手)

方寸斗室小天地正氣迷漫大世界

數(shù)學(xué)EPI: 7
應(yīng)助: 157 (高中生)
貴賓: 0.927
金幣: 9349.6
散金: 4503
紅花: 77
沙發(fā): 2
帖子: 2745
在線: 1465.6小時
蟲號: 3086598
注冊: 2014-03-25
管轄: 數(shù)學(xué)

【答案】應(yīng)助回帖

★ ★ ★ ★ ★
感謝參與，應(yīng)助指數(shù) +1
375291258: 金幣+5, ★★★很有幫助 2014-10-13 20:58:59

命題設(shè)p和q是不同的素數(shù)，則存在模p和q的一個公共原根。
證明：
情形一： $p=2,q>2$
由于q為素數(shù)，模2q有原根，設(shè)g是模2q的一個原根（不妨設(shè)g是奇數(shù)）
則g也是q的一個原根，g也是2的一個原根
所以g是2和q的一個公共原根。
情形二： $p>2,q>2$ ，p和q是不同的奇素數(shù)。
不妨設(shè) $p>q$ ，則有 $p-1>q$
由于p為素數(shù)，故模p有原根g（不妨設(shè)g是奇數(shù)）
則 $g,g^2,g^3,\cdots,g^{p-1}$ 是模p的既約剩余系
因為q為素數(shù)，所以 $g^i(i=1,2,\cdots,p-1)$ 與q互素
根據(jù)帶余數(shù)除法，可以設(shè) $g^i\equiv r_i(i=1,2,\cdots,p-1)(modq)$ ，這里 $r_i\in[0,q-1](i=1,2,\cdots,p-1)$ 是整數(shù)
由于p-1個 $r_i$ 取q個值， $p-1>q$ ，由鴿子籠原理知道必有兩個相等，不妨設(shè) $r_i=r_j(i<j)$ ，
則 $g^{j-i}\equiv 1(modq)$ ，
從而易知 $g^{j-i}$ 是模q的一個原根，
又由g的構(gòu)造知道 $g^{j-i}$ 是模p的一個原根，
所以 $g^{j-i}$ 是模p和模q的一個公共原根。
綜合上面兩種情況即知命題為真。

贊一下

回復(fù)此樓

青蔥歲月圣誕夜，浪漫歌舞迎新年。

2樓2014-10-13 10:14:14

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

hank612

至尊木蟲 (著名寫手)

數(shù)學(xué)EPI: 14
應(yīng)助: 225 (大學(xué)生)
金幣: 14270.6
散金: 1055
紅花: 95
帖子: 1526
在線: 1375.8小時
蟲號: 2530333
注冊: 2013-07-03
性別: GG
專業(yè): 理論和計算化學(xué)

設(shè)a是p的原根，b是q的原根，那么
x= a*q^2+b*p^2
滿足 $x^{\frac{p-1}{2}}\equiv a^{\frac{p-1}{2}} \equiv -1 (mod p), x^{\frac{q-1}{2}}\equiv b^{\frac{q-1}{2}} \equiv -1 (mod q)$
因此x是公共原根。

贊一下(1人)

回復(fù)此樓

We_must_know. We_will_know.

3樓2014-10-13 11:02:33

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

375291258

鐵桿木蟲 (著名寫手)

應(yīng)助: 1 (幼兒園)
金幣: 11067.5
散金: 33
帖子: 2982
在線: 74.1小時
蟲號: 1858830
注冊: 2012-06-14
性別: GG
專業(yè): 組合數(shù)學(xué)

引用回帖:

2樓: Originally posted by Edstrayer at 2014-10-13 10:14:14
命題設(shè)p和q是不同的素數(shù)，則存在模p和q的一個公共原根。
證明：
情形一：p=2,q>2
由于q為素數(shù)，模2q有原根，設(shè)g是模2q的一個原根（不妨設(shè)g是奇數(shù)）
則g也是q的一個原根，g也是2的一個原根
所以g是2和q的一 ...

g^(j-i)=1(mod q)
從而易知是g^(j-i)模q的一個原根，這個不理解，請教一下！謝謝！

贊一下

回復(fù)此樓

4樓2014-10-13 21:28:10

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

Edstrayer

版主 (著名寫手)

方寸斗室小天地正氣迷漫大世界

數(shù)學(xué)EPI: 7
應(yīng)助: 157 (高中生)
貴賓: 0.927
金幣: 9349.6
散金: 4503
紅花: 77
沙發(fā): 2
帖子: 2745
在線: 1465.6小時
蟲號: 3086598
注冊: 2014-03-25
管轄: 數(shù)學(xué)

引用回帖:

4樓: Originally posted by 375291258 at 2014-10-13 21:28:10
g^(j-i)=1(mod q)
從而易知是g^(j-i)模q的一個原根，這個不理解，請教一下！謝謝！...

根據(jù)原根的定義直接驗證。

贊一下

回復(fù)此樓

青蔥歲月圣誕夜，浪漫歌舞迎新年。

5樓2014-10-14 05:44:39

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

375291258

鐵桿木蟲 (著名寫手)

應(yīng)助: 1 (幼兒園)
金幣: 11067.5
散金: 33
帖子: 2982
在線: 74.1小時
蟲號: 1858830
注冊: 2012-06-14
性別: GG
專業(yè): 組合數(shù)學(xué)

引用回帖:

5樓: Originally posted by Edstrayer at 2014-10-14 05:44:39
根據(jù)原根的定義直接驗證。...

按你的說法，我能不能這樣想 g是p原根，則g=1(mod p), 從而
g^2=1(mod p),...,g^(p-2)=1(mod p), 這樣是不是與g,g^2,),...,g^(p-2)是模p的既約剩余系矛盾。

贊一下

回復(fù)此樓

6樓2014-10-15 20:55:09

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

Edstrayer

版主 (著名寫手)

方寸斗室小天地正氣迷漫大世界

數(shù)學(xué)EPI: 7
應(yīng)助: 157 (高中生)
貴賓: 0.927
金幣: 9349.6
散金: 4503
紅花: 77
沙發(fā): 2
帖子: 2745
在線: 1465.6小時
蟲號: 3086598
注冊: 2014-03-25
管轄: 數(shù)學(xué)

引用回帖:

6樓: Originally posted by 375291258 at 2014-10-15 20:55:09
按你的說法，我能不能這樣想 g是p原根，則g=1(mod p), 從而
g^2=1(mod p),...,g^(p-2)=1(mod p), 這樣是不是與g,g^2,),...,g^(p-2)是模p的既約剩余系矛盾。...

證法二：
因為p是素數(shù)，p有原根a
因為q是素數(shù)，q有原根b
則與a模p同余的數(shù)都是模p的原根
與b模q同余的數(shù)都是模q的原根
由于p，q是互不相同的素數(shù)
由中國剩余定理知道，存在整數(shù)x，使得：

$\left\{\begin{array}{c}x\equiv a(modp)\\x\equiv b(modq)\end{array}\right.$

則x是模p和模q的公共原根。

贊一下(1人)

回復(fù)此樓

青蔥歲月圣誕夜，浪漫歌舞迎新年。

7樓2014-10-16 03:55:53

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

相關(guān)版塊跳轉(zhuǎn) 我要訂閱樓主 375291258 的主題更新

返回列表

最具人氣熱帖推薦 [查看全部]		作者	回/看	最后發(fā)表

[考研] 307求調(diào)劑 +9	冷笙123 2026-03-17	9/450	2026-03-19 22:44 by 學(xué)員8dgXkO
[考研] 265求調(diào)劑 +3	梁梁校校 2026-03-19	3/150	2026-03-19 22:34 by 學(xué)員8dgXkO
[考研] 321求調(diào)劑 +8	何潤采123 2026-03-18	10/500	2026-03-19 16:46 by 何潤采123
[考研] 0703化學(xué)調(diào)劑 +4	18889395102 2026-03-18	4/200	2026-03-19 16:13 by 30660438
[考研] 304求調(diào)劑 +3	曼殊2266 2026-03-18	3/150	2026-03-19 14:42 by peike
[考研] 材料080500調(diào)劑求收留 +4	一顆meteor 2026-03-13	4/200	2026-03-19 10:32 by 30660438
[教師之家] 焦慮 +9	水冰月月野兔 2026-03-13	13/650	2026-03-19 09:50 by otani
[考研] 085410人工智能專碩317求調(diào)劑（0854都可以） +3	xbxudjdn 2026-03-18	3/150	2026-03-18 22:14 by zhq0425
[考研] 311求調(diào)劑 +4	冬十三 2026-03-18	4/200	2026-03-18 21:47 by 盡舜堯1
[考研] 311求調(diào)劑 +11	冬十三 2026-03-15	12/600	2026-03-18 14:36 by 星空星月
[考研] 一志愿蘇州大學(xué)材料工程（085601）專碩有科研經(jīng)歷三項國獎兩個實用型專利一項省級立項 +6	大火山小火山 2026-03-16	8/400	2026-03-17 15:05 by 無懈可擊111
[考研] 考研調(diào)劑 +3	淇ya_~ 2026-03-17	5/250	2026-03-17 09:25 by Winj1e
[考研] 11408 一志愿西電，277分求調(diào)劑 +3	zhouzhen654 2026-03-16	3/150	2026-03-17 07:03 by laoshidan
[考研] 中科院材料273求調(diào)劑 +4	yzydy 2026-03-15	4/200	2026-03-16 15:59 by Gaodh_82
[考研] 0703化學(xué)調(diào)劑 290分有科研經(jīng)歷，論文在投 +7	膩膩gk 2026-03-14	7/350	2026-03-16 10:12 by houyaoxu
[考研] 0856求調(diào)劑 +3	劉夢微 2026-03-15	3/150	2026-03-16 10:00 by houyaoxu
[考研] 0856專碩279求調(diào)劑 +5	加油加油！? 2026-03-15	5/250	2026-03-15 11:58 by 2020015
[考研] 289求調(diào)劑 +4	這么名字咋樣 2026-03-14	6/300	2026-03-14 18:58 by userper
[考研] 328求調(diào)劑 +3	5201314Lsy！ 2026-03-13	6/300	2026-03-14 15:31 by hyswxzs
[考研] 297求調(diào)劑 +4	學(xué)海漂泊 2026-03-13	4/200	2026-03-14 11:51 by 熱情沙漠