$($e$)$ Implement a classical function to find the order of $$a modulo $$n where $,$a$,$n are inputs.

what i have :

def gcd$($m$,$ n$)$:

while n:

m$,$ n $=$ n$,$ m $\%$ n

return m

def modular$\_$exponentiate$($a$,$ k$,$ n$)$:

res $=1$

while k $>0$:

if k $\%2==1$:

res $=($res $*$ a$)\%$ n

a $=($a $*$ a$)\%$ n

k $//=2$

return res

def find$\_$order$($a$,$ n$)$:

for r in range$(1,$ n$)$:

if modular$\_$exponentiate$($a$,$ r$,$ n$)==1$:

return r

return None

Write a function count$\_$hits$($n$)$ that runs through all numbers $$a from $22$ to $1$n$1,$ ignoring the ones for which $(,)1$GCD$($a$,$n$)1($in which case we will find a factor purely by chance$)$ and counts the number of "hits" wherein a hit happens for $$a iff

what i have for this cell:

def gcd$($m$,$ n$)$:

while n:

m$,$ n $=$ n$,$ m $\%$ n

return m

def modular$\_$exponentiate$($a$,$ k$,$ n$)$:

res $=1$

while k $>0$:

if k $\%2==1$:

res $=($res $*$ a$)\%$ n

a $=($a $*$ a$)\%$ n

k $//=2$

return res

def find$\_$order$($a$,$ n$)$:

for r in range$(1,$ n$)$:

if modular$\_$exponentiate$($a$,$ r$,$ n$)==1$:

return r

return None

# Example usage:

print$($find$\_$order$(4,7))$ # This will return the order of $4$ mod $7$

def count$\_$hits$($n$)$:

hits $=0$

for a in range$(2,$ n$)$:

if gcd$($a$,$ n$)==1$: # a and n must be relatively prime

r $=$ find$\_$order$($a$,$ n$)$

if r is not None and r $\%2==0$: # Order must be even

if $($modular$\_$exponentiate$($a$,$ r $//2,$ n$)+1)\%$ n $==0$:

hits $+=1$

return hits

Cell that I can't change :

h$15=$ count$\_$hits$(15)$

print$($f$\text{'}$count$\_$hits$(15)=\{$h$15\}\text{'})$

assert h$15==6$ # hits for $15$ are $2,4,7,8,11,13$

# note that $\backslash$varphi$(15)=2*4=8$

print$($f$\text{'}$Fraction of hits among relatively prime $=\{$h$15/(2*4)\}\text{'})$

h$77=$ count$\_$hits$(77)$ # there should be $46$ hits for $77$

print$($f$\text{'}$count$\_$hits$(77)=\{$h$77\}\text{'})$

assert h$77==30$

# note that $\backslash$varphi$(77)=6*10=60$

print$($f$\text{'}$Fraction of hits among relatively prime $=\{$h$77/(60)\}\text{'})$

h$91=$ count$\_$hits$(91)$

print$($f$\text{'}$count$\_$hits$(91)=\{$h$91\}\text{'})$

assert h$91==54$

# note $\backslash$varphi$(91)=12*6=72$

print$($f$\text{'}$Fraction of hits among relatively prime $=\{$h$91/(72)\}\text{'})$

h$111=$ count$\_$hits$(111)$ # there whould be $92$ hits

print$($f$\text{'}$count$\_$hits$(111)=\{$h$111\}\text{'})$

assert h$111==54$

# note $\backslash$varphi$(111)=36*2=72$

print$($f$\text{'}$Fraction of hits among relatively prime $=\{$h$111/(72)\}\text{'})$

h$893=$ count$\_$hits$(893)$

print$($f$\text{'}$count$\_$hits$(893)=\{$h$893\}\text{'})$

assert h$893==414$

assertion error I get:

count$\_$hits$(15)=1$

$---------------------------------------------------------------------------$ AssertionError Traceback $($most recent call last$)$ Cell In$[197],$ line $31$ h$15=$ count$\_$hits$(15)2$ print$($f$\text{'}$count$\_$hits$(15)=\{$h$15\}\text{'})---->3$ assert h$15==6$ # hits for $15$ are $2,4,7,8,11,134$ # note that $\backslash$varphi$(15)=2*4=85$ print$($f$\text{'}$Fraction of hits among relatively prime $=\{$h$15/(2*4)\}\text{'})$ AssertionError:

thanks for your help!