【趣题征解】求一个正整数 n，使得 3^n ≡ 2  mod （n）

天山草

[这个贴子最后由天山草在 2011/09/03 07:52pm 第 3 次编辑]

求一个正整数 n， 使得 3^n ≡ 2  mod （n）
如果您认为这样的 n 是不存在的，那就证明它不存在。
不管您相信不相信，反正我是相信：确实有这样的 n 存在，尽管它极其稀少，少得如同大海里的一滴水。

wangyangkee

[这个贴子最后由wangyangkee在 2011/10/10 04:12pm 第 2 次编辑]

胡思乱想------
假设     3^n ≡ 2 （mod n）    成立，设 3^n -2=nk
那么，  nk是3的倍数+1
显然，n只能是奇数；nk同是3的倍数+1   或者  nk同是3的倍数+2
那么，   nk是3的倍数+1，不外乎
nk=30的倍数+1,7,13,19；
由此  3^n= 30的倍数+3,9,15,21；
而3的奇数幂不外乎
3^n= 30的倍数+3,27；
n的两个约束条件结合是
3^n= 30的倍数+3     由此nk是30的倍数+1
而且   n是4的倍数+1
同时，3^n= 240的倍数+3，nk是240的倍数+1
nk是240的倍数+1决定
n是240的倍数+1，k也是240的倍数+1
下面的无法进行，，，

w632158

[这个贴子最后由w632158在 2011/09/03 09:27pm 第 1 次编辑]

下面引用由awei在 2011/09/03 09:12pm 发表的内容：
n=6，3^6-1=728,    728除以6余2

给出的反例不合题意，原题是没有减1才余2的。

w632158

luyuanhong

[这个贴子最后由luyuanhong在 2011/09/03 10:30pm 第 1 次编辑]

下面引用由天山草在 2011/09/03 01:48pm 发表的内容：
求一个正整数 n， 使得 3^n ≡ 2  mod （n）
如果您认为这样的 n 是不存在的，那就证明它不存在。
不管您相信不相信，反正我是相信：确实有这样的 n 存在，尽管它极其稀少，少得如同大海里的一滴水。

【题】是否有正整数 n ，使得 3^n≡2(mod n) ？

【答】初步可以得到下面几点结论：

（1）当 n 是偶数时，3^n 除以 n 的余数一定是奇数，不可能是 2 。

    因为 3^n 是奇数，n 是偶数，所以 3^n 除以 n 的余数一定是奇数。

（2）当 n 是 3 的倍数时，3^n 除以 n 的余数一定是 3 的倍数，不可能是 2 。

    因为 3^n 是 3 的倍数，n 是 3 的倍数，3^n 除以 n 的余数是 3 的倍数。

（3）当 n 是大于 3 的素数时，3^n 除以 n 的余数一定是 3 ，不可能是 2 。

    因为根据欧拉定理，当 n 是大于 3 的素数时，(n,3)＝1 ，3^(n-1)≡1(mod n) ，
所以必有 3^n≡3(mod n) ，即 3^n 除以 n 的余数是 3  。

（4）剩下只有一种情形： n 为不是 3 的倍数的奇合数的情形。

例如，n＝5×5＝25 时，3^25 除以 25 的余数是 18 ，
      n＝5×7＝35 时，3^35 除以 35 的余数是 12 ，
      n＝7×7＝49 时，3^49 除以 49 的余数是 31 ，
      n＝5×11＝55 时，3^55 除以 55 的余数是 12 ，
      n＝5×13＝65 时，3^65 除以 65 的余数是 48 ，
      n＝7×11＝77 时，3^77 除以 77 的余数是 75 ，
      n＝5×17＝85 时，3^85 除以 85 的余数是 73 ，
      n＝7×13＝91 时，3^91 除以 91 的余数是 3 ，
      n＝5×19＝95 时，3^95 除以 95 的余数是 72 ，
      n＝5×23＝115 时，3^115 除以 115 的余数是 82 ，
      n＝7×17＝119 时，3^119 除以 119 的余数是 96 ，
      n＝11×11＝121 时，3^121 除以 121 的余数是 3 ，
      ……

wangyangkee

[这个贴子最后由wangyangkee在 2011/09/06 02:28pm 第 2 次编辑]

------------------------------

luyuanhong

下面引用由awei在 2011/09/04 00:33am 发表的内容：
所以n只能是能被5整除的奇合数

当 n＝7×7＝49 时，φ(n)＝φ(49)＝42 。
6^φ(n)＝6^φ(49)＝6^42＝481229803398374426442198455156736≡1（mod 49）。
也就是说，当 n＝49 时，有 6^φ(n)-1≡0(mod n) ，但 n 不是 5 的倍数。

LLZ2008

n=45时， 3^45 ≡ 2 （mod 45）
设n=3^k*p，3^m≡ 2 （mod ）,若（(p-1)|(n-k-m),则3^(3*k*p) ≡ 2 （mod 3^k*p）,其中p为素数。

luyuanhong

下面引用由LLZ2008在 2011/09/04 06:29am 发表的内容：
n=45时， 3^45 ≡ 2 （mod 45）
设n=3^k*p，3^m≡ 2 （mod ）,若（(p-1)|(n-k-m),则3^(3*k*p) ≡ 2 （mod 3^k*p）,其中p为素数。

3^45＝2954312706550833698643≡18（mod 45) 。
即有
65651393478907415525×45＋18＝2954312706550833698625＋18＝2954312706550833698643＝3^45

天山草

热烈欢迎各位大师光临本帖！
陆教授分析得十分正确：n 为不是 3 的倍数的奇合数。
本人在一百万以内只找到了一个满足要求的数。
本人猜想，也许此数是“只此一家，别无分店”，就是说，若是继续在大于一百万的整数里面找，恐怕是再也找不到鸟。