# Math Help - reduction mod

1. ## reduction mod

let n=1105, so n-1=2^4(69) Compute the values of

2^69(mod1105), 2^2*69(mod 1105), 2^4*69(mod1105), 2^8*69(mod1105),

Use the Rabin Miller test to conclue that n is composite....

Where do I begin and how?

2. Originally Posted by duggaboy
let $n=1105,$ so $n-1=2^4\times 69$ Compute the values of

$[2^{69} \mod 1105],\ [2^{2 \times 69} \mod 1105],\ [2^{4 \times 69}\mod 1105],\ [2^{8 \times 69} \mod 1105]$

Use the Rabin Miller test to conclue that n is composite....

Where do I begin and how?
In the Rabin-Miller test for the (pseudo) primality of $1105$ we have $s=4$ and $d=69$

So $a$ is a witness to the primallity of $1105$ if:

$
a^d \not \equiv 1 \mod 1105
$

and

$
a^{2^r.d} \not \equiv -1 \mod 1105; \forall \ r \in \{0,\ ..., \ s-1\}
$

So if you compute the values asked for and the first is not congruent to $\pm 1 \mod 1105$ and the others are not congruent to $-1 \mod 1105$, then $2$ is a witness to the compositness of $1105$. (In fact if the conditions hold then 1105 is certainly composite, if they fail 1105 is probably prime)

RonL

3. Can you explain the last part of this to me?

4. Originally Posted by duggaboy

Can you explain the last part of this to me?
It is that these:

"2^69(mod1105), 2^2*69(mod 1105), 2^4*69(mod1105), 2^8*69(mod1105)"

are not congruent to -1 modulo 1105.

RonL