一、本章作业

1.证明： 91是对于基3的拟素数.

2.证明： 45是对于基17和基19的拟素数.

3.证明： 25是基于7的强拟素数.

二、答案

1．证明：因为91=13*7是奇合数，       (3,91)=1

         又3⁶=729≡1(mod91)    则3^91-1=3⁹⁰≡(3⁶)¹⁵≡1(mod91)

         则91是对于基3的拟素数。

2．证明：因为45=5*3*3是奇合数，       (17,45)=1

         由Euler定理：17⁴≡1(mod5)      17²≡1(mod3)

         所以17⁴≡1(mod3)      所以17⁴≡1(mod45)

         则17^45-1=17⁴⁴≡(17⁴)¹¹≡1(mod45)

         则45是对于基17的拟素数。

      同理45是对于基19的拟素数。

3．证明：25=5*5是奇素数 设n=25 n-1=24=2³*3   则t=3    (7,25)=1

          7³≡18(mod25)    7^2*3≡-1(mod25)

          所以25是基于7的强拟素数。

一、本章作业

1.证明： 91是对于基3的拟素数.

2.证明： 45是对于基17和基19的拟素数.

3.证明： 25是基于7的强拟素数.

二、答案

1．证明：因为91=13*7是奇合数，       (3,91)=1

         又3⁶=729≡1(mod91)    则3^91-1=3⁹⁰≡(3⁶)¹⁵≡1(mod91)

         则91是对于基3的拟素数。

2．证明：因为45=5*3*3是奇合数，       (17,45)=1

         由Euler定理：17⁴≡1(mod5)      17²≡1(mod3)

         所以17⁴≡1(mod3)      所以17⁴≡1(mod45)

         则17^45-1=17⁴⁴≡(17⁴)¹¹≡1(mod45)

         则45是对于基17的拟素数。

      同理45是对于基19的拟素数。

3．证明：25=5*5是奇素数 设n=25 n-1=24=2³*3   则t=3    (7,25)=1

          7³≡18(mod25)    7^2*3≡-1(mod25)

          所以25是基于7的强拟素数。