# Thread: congruence problem

1. ## congruence problem

suppose b is congruent to a^67 (mod 91) and (a,91)=1 (gcd) for some a,b element of Z such that 0<=a<91.

1) find k element of Z such that b^k is congruent to a (mod 91)
2) let b=53. Find a

i think 1 & 2 need to be done as separate questions but I have NO clue how to do this.

any help is appreciated.

2. Are we doing all your homework tonight?

1)
$b \equiv a^{67} \mod 91$
$b^k \equiv a^{67k} \mod 91$

So you want to find $k$ such that $67k \equiv 1 \mod 91$; i.e. you want to find the inverse of 67 in the group $(\mathbb{Z}/91\mathbb{Z})^\times$. To do this, note that for any $x \in (\mathbb{Z}/91\mathbb{Z})^\times$, $x^{\phi(91)}=1$; hence $67^{\phi(91)}=1$, or $67(67^{\phi(91)-1})=1$... can you finish now?

3. no, i have no idea how to finish.

4. Originally Posted by Bruno J.
So you want to find $k$ such that $67k \equiv 1 \mod 91$
Actually, you have $\varphi(91)=72$ (where $\varphi$ is the Euler function) so $a^{72}\equiv1\,(\bmod\,91).$

So you want to find $k$ such that $67k\equiv1\,(\bmod\,\color{red}72\color{black})$ (not mod 91).