有序数对的个数.

Tesla35

考虑有序数对$(m,n)$,使得$m,n$是集合$\{1,2,\cdots,30\}$中的正整数,并且$2^m+1$和$2^n-1$的最大公约数不是1.求所有这样的有序数对的个数.

tommywong

n=2:   m=1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,
n=4:   m=1,2,3,5,6,7,9,10,11,13,14,15,17,18,19,21,22,23,25,26,27,29,30,
n=6:   m=1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,
n=8:   m=1,2,3,4,5,6,7,9,10,11,12,13,14,15,17,18,19,20,21,22,23,25,26,27,28,29,30,
n=10: m=1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,
n=12: m=1,2,3,5,6,7,9,10,11,13,14,15,17,18,19,21,22,23,25,26,27,29,30,
n=14: m=1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,
n=16: m=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,17,18,19,20,21,22,23,24,25,26,27,28,29,30,
n=18: m=1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,
n=20: m=1,2,3,5,6,7,9,10,11,13,14,15,17,18,19,21,22,23,25,26, 27,29,30,
n=22: m=1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,
n=24: m=1,2,3,4,5,6,7,9,10,11,12,13,14,15,17,18,19,20,21,22, 23,25,26,27,28,29,30,
n=26: m=1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,
n=28: m=1,2,3,5,6,7,9,10,11,13,14,15,17,18,19,21,22,23,25,26,27,29,30,
n=30: m=1,3,5,7,9,11,13,15,17,19,21,23,25,27,29
probably have 規律

Czhang271828

回复 2# tommywong

原解答以繁琐故隐藏, 较简洁的解答见下两楼.

Guest, if you want to see the hidden content, please Reply

tommywong

$\begin{cases}
n\equiv 1\pmod{2} & 1\nmid m\\
n\equiv 2\pmod{4}, & 2\nmid m\\
n\equiv 4\pmod{8}, & 4\nmid m\\
n\equiv 8\pmod{16}, & 8\nmid m\\
n\equiv 16\pmod{32}, & 16\nmid m\\
n\equiv 2^k\pmod{2^{k+1}}, & 2^k\nmid m\\
\end{cases}$時$(2^m+1,2^n-1)>1$

$\begin{cases}
n\equiv 1\pmod{2} & 1\mid m\\
n\equiv 2\pmod{4}, & 2\mid m\\
n\equiv 4\pmod{8}, & 4\mid m\\
n\equiv 8\pmod{16}, & 8\mid m\\
n\equiv 16\pmod{32}, & 16\mid m\\
n\equiv 2^k\pmod{2^{k+1}}, & 2^k\mid m\\
\end{cases}$時$(2^m+1,2^n-1)=1$

30*30-(15*30+8*15+4*7+2*3+1*1)=295

Czhang271828

回复 4# tommywong

帮您验证一下猜想, 也算重新解答 (之前的忽视吧).

证明: $n\equiv 2^k\mod 2^{k+1}$ 时, $\gcd(2^{n}-1,2^m+1)=1$ 若且仅若 $2^k\mid m$.

必要性: 若 $\gcd(2^{n}-1,2^m+1)=1$, 则
$$
1=\dfrac{\gcd(2^{n}-1,2^{2m}-1)}{\gcd(2^{n}-1,2^m-1)}=\dfrac{2^{\gcd (n,2m)}-1}{2^{\gcd(n,m)}-1}.
$$
分子分母相等, 故 $2^k\mid m$.

充分性: 此时 $\gcd(2^{n}-1,2^{2m}-1)=\gcd(2^{n}-1,2^{m}-1)=2^{2^k}-1$. $2^{2^k}-1$ 中可能混入了 $2^m+1$​ 的某些因子, 但实际上不可能, 因为对任意 $m=l \cdot 2^k$ 均有
$$
\begin{align*}
\gcd(2^{2^k}-1,2^m+1)=&\gcd (2^{2^k}-1,(2^{2^k}-1+1)^l+1)\\
=&\gcd (2^{2^k}-1,2)\\
=&1.
\end{align*}
$$

在上一层给出的分类思路下, 好像确实就这么简单.

注: 引理 $\gcd(2^a-1,2^b-1)=2^{\gcd(a,b)}-1$, $\forall a,b\in\mathbb N_+$.

证明: 一方面, 右式为左式的因子; 另一方面, 对任意左式包含的极大质数幂 $p_i^{n_i}$ 总有 $2^a\equiv 2^b\equiv 2^{\gcd(a,b)}\equiv 1\mod p_i ^{n_1}$, 从而左式为右式的因子. 综上, 两侧相等.

tommywong

回复 5# Czhang271828

我覺得充分性應該咁樣證
$2^k\mid m\implies \gcd (n,2m)=\gcd(n,m)$
$\gcd(2^n-1,2^m+1)=\dfrac{\gcd(2^{n}-1,2^{2m}-1)}{\gcd(2^{n}-1,2^m-1)}
=\dfrac{2^{\gcd (n,2m)}-1}{2^{\gcd(n,m)}-1}=1$

Czhang271828

回复 6# tommywong

$\gcd(a,b)=\dfrac{\gcd(a,bc)}{\gcd(a,c)}$ 不一定吧. $\gcd(2,2)=\dfrac{\gcd(2,4)}{\gcd(2,2)}$?

形象地说, 可能"混入相同因子"以造成干扰了, 这也是我证明多花两行的原因.

tommywong

回复 7# Czhang271828

唔駛，$2^m+1$跟$2^m-1$互質

Czhang271828

回复 8# tommywong

真系多谢晒, 而家头晕身㷫中气衰咁显然嘢仲唔识睇,,,,

tommywong

GCD of 2^n-1 and 2^m+1

$(x^n-1,x^m+1)=\begin{cases}(x-1,2) & \nu_2(n)\le \nu_2(m)\\
x^{(n,m)}+1 & \nu_2(n)\ge \nu_2(m)+1\end{cases}$