Discrete Mathematics - Modular arithmethics

Question

I've been trying to solve a task for some while now but I'm currently very stuck.

For the integers $a$ and $b$ it applies that $b \equiv a \pmod{91}$ and $\gcd (a, 91) = 1$. Determine a positive number $k> 1$ such that $b^k \equiv a \pmod{91}.$

I know that $b^{\phi(91)} = 1\pmod{91}$ and $b^{\phi(91)} = 72$.

After this I'm pretty empty. Would anyone be so kind to guide me or help me in the right direction?

Hello guys, sorry for the translate error. SGD is biggest common divider! — mathNemesis, Nov 05 '20 at 15:28
@gt6989b Hey, its exactly what it is, greatest common divisor, I used google translate and I forgot that part, thanks for letting me know. — mathNemesis, Nov 05 '20 at 15:29
Do you mean like $27^3\equiv 27\mod 91;;64^3\equiv 64\mod 91;;90^3\equiv 90\mod 91$ — Raffaele, Nov 05 '20 at 15:42
@Raffaele To be honest at this point im not even sure what im looking for myself. — mathNemesis, Nov 05 '20 at 16:56
@Rocky abiessu means that $a^{73}\equiv a \mod 91$ for any $0\le a\le 90$. The reason of $+1$ should be quite clear, since $a^{\phi(91)}\equiv 1 \mod 91$. — Raffaele, Nov 05 '20 at 18:33
@Raffaele Thanks alot, I get it a little more now. But im supposed to find the value between 0 and 90 then? — mathNemesis, Nov 05 '20 at 21:57
@Raffaele could you assist me some moer on this task? Im not so sure what I should focus on trying to do. — mathNemesis, Nov 06 '20 at 10:34
@Raffaele Hello, I have been more succesful in coming forward but I still doesnt realise why we add the +1. Its not very obvious im sad to say. I understand why we take Eulerphi and that it is 72 but the +1 doesnt make sense to me. — mathNemesis, Nov 07 '20 at 14:33

abiessu · Answer 1 · 2020-11-10T14:27:57.503

1

Since we have $a\equiv b\mod 91$ and also $\varphi(91)=72$ added to $(a,91)=(b,91)=1$ giving $b^{72}\equiv 1\mod 91,$ then we can say $b\cdot b^{72}\equiv b\cdot 1\equiv a\equiv b^{73}\mod 91$.

Thus $b^k\equiv a\mod 91$ using $k=\varphi(91)+1$.

edited Nov 10 '20 at 14:27

answered Nov 07 '20 at 17:05

abiessu

8,115

score 0 · Answer 2 · answered Nov 08 '20 at 07:54

$k$ calculate as discrete logarithm by modulo $91$ and have form $k=r\pmod{m}$, where $r$=2..11 and $m$=3,4,6,12.

gp-code:

k91()=
{
 K= [];
 for(a=0, 90, if(gcd(a,91)==1, for(b=0, 90, if(gcd(b,91)==1,
  m= Mod(b, 91);
  h= znorder(m);
  k= znlog(a, m, h);
  if(k, if(k>1,
   K= concat(K, [[k,h]]);
  ))
 ))));
 print(vecsort(K,,8))
};

Output [r,m]:

[[2, 3], [2, 4], [2, 6], [2, 12], [3, 4], [3, 6], [3, 12], [4, 6], [4, 12], [5, 6], [5, 12], [6, 12], [7, 12], [8, 12], [9, 12], [10, 12], [11, 12]]

Discrete Mathematics - Modular arithmethics

2 Answers2