Mod Complexity

[Anood]

Please help me in the following

Let R(b,k) (n)be the least number of atomic operations required to compute
the remainder of an n-digit number mod k when working with numbers given as
strings in base b.

1.Show that if k |b,then R(b,k) (n)=1.
2.Show that if every prime that divides k also divides b,then Rb,k (n)=O(1).
3.Prove that in all other cases Rb,k (n)= theta(n).
Note that in all cases we are talking about running time in terms of n.You may regard b,k as
fixed constants.
*Note that:
f(x)=O(g(x))iff there exists C >0,N such that for all x
>N,|f(x)|<= C |g(x)|

•f(x)=omega(g(x))iff there exists C >0,N such that for all x
>N,|f(x)|>=C |g(x)|
•f(x)=theta(g(x))iff f(x)=O(g(x))and f(x)=omega
(g(x)).

 

[pka]

I think that you should find a very specialized board on which to post this question. It appears to me as if it is from a course in discrete mathematics of engineers (perhaps computer engineering). Although I have taught discrete mathematics, I have no idea what the particular terms and symbols in your question mean. Without a complete listing of definitions and symbols, I do not think we can be of help.

 

[Anood]

The first question is asking me to show that i think i just need to check one digit of a base-b number in order to find the remainder after division by k, when k is a factor of b. (i don't know how to show that)!

Now, do you see how question 2 relates to the rule for finding the remainder of division by 4 for base-10 numbers?

Finally, do you see how question 3 relates to the fact that for numbers like 7, whose prime factors don't divide 10, there's no quicker method than visiting every digit of the number?

(i understand the questions but i don't know how to solve them)

 

[pka]

You are in need of a sit-down with you instructor