Разделы 
Дополнительно
Задача по математике - 13171
2023-07-09 
$2^{p} - 1$ и $2^{q} - 1$ взаимно просты. Доказать, что $p$ и $q$ - так же взаимно просты. Обратно, если $p$ и $q$ - взаимно просты, то и $2^{p} - 1$ и $2^{q} - 1$ взаимно просты.
Решение:
Пусть $p$ и $q$ имеют общий делитель $d$, тогда $p = p_{1}d, q = q_{1}d$.
$2^{p} - 1 = (2^{d})^{p_{1}} - 1 = (2^{d} - 1) \cdot (2^{d(p_{1} - 1)} + 2^{d(p_{1} - 2)} + \cdots + 1)$,
$2^{q} - 1 = (2^{d})^{q_{1}} - 1 = (2^{d} - 1) \cdot (2^{d(q_{1} - 1)} + 2^{d(q_{1} - 2)} + \cdots + 1)$,
Следовательно, если $2^{p} - 1$ и $2^{q} - 1$ взаимно просты, то $p$ и $q$ также взаимно просты, т.е. $d = 1$.
Пусть теперь $p$ и $q$ взаимно просты и $p > q$. Если $d$ - общий делитель чисел $2^{p} - 1$ и $2^{q} - 1$, то $d$ - делитель также числа $2^{p} = 2^{q} = 2^{q} \cdot (2^{p-q} - 1)$. Так как $2^{k} - 1$ на 2 не делится ($k > 0$), то $2^{p -q} - 1$ делится на $d$. Если еще $p - q > q$, то рассуждая аналогично получим, что $2^{p - lq} - 1$ делится на $d$, где $p - lq < q$. Обозначим $p - lq = q_{1}$ и, повторяя рассуждения, найдем $l_{1}$ такое, что $2^{q - l_{1}q_{1}} - 1$ делится на $d$, где $q - l_{1}q_{1} < q_{1}$. Так дойдем до $q_{i} = 1$, т.е. 2 - 1 = 1 делится на $d$, значит, $d= 1$.
$2^{p} - 1$ и $2^{q} - 1$ взаимно просты. Доказать, что $p$ и $q$ - так же взаимно просты. Обратно, если $p$ и $q$ - взаимно просты, то и $2^{p} - 1$ и $2^{q} - 1$ взаимно просты.
Решение:
Пусть $p$ и $q$ имеют общий делитель $d$, тогда $p = p_{1}d, q = q_{1}d$.
$2^{p} - 1 = (2^{d})^{p_{1}} - 1 = (2^{d} - 1) \cdot (2^{d(p_{1} - 1)} + 2^{d(p_{1} - 2)} + \cdots + 1)$,
$2^{q} - 1 = (2^{d})^{q_{1}} - 1 = (2^{d} - 1) \cdot (2^{d(q_{1} - 1)} + 2^{d(q_{1} - 2)} + \cdots + 1)$,
Следовательно, если $2^{p} - 1$ и $2^{q} - 1$ взаимно просты, то $p$ и $q$ также взаимно просты, т.е. $d = 1$.
Пусть теперь $p$ и $q$ взаимно просты и $p > q$. Если $d$ - общий делитель чисел $2^{p} - 1$ и $2^{q} - 1$, то $d$ - делитель также числа $2^{p} = 2^{q} = 2^{q} \cdot (2^{p-q} - 1)$. Так как $2^{k} - 1$ на 2 не делится ($k > 0$), то $2^{p -q} - 1$ делится на $d$. Если еще $p - q > q$, то рассуждая аналогично получим, что $2^{p - lq} - 1$ делится на $d$, где $p - lq < q$. Обозначим $p - lq = q_{1}$ и, повторяя рассуждения, найдем $l_{1}$ такое, что $2^{q - l_{1}q_{1}} - 1$ делится на $d$, где $q - l_{1}q_{1} < q_{1}$. Так дойдем до $q_{i} = 1$, т.е. 2 - 1 = 1 делится на $d$, значит, $d= 1$.
