Then you have
How would one go about in order to prove
I would try doing something like this
however I'm not sure how to actually interpret . It's periodic function which returns remainders and repeatedly so, what would it's algebraic expression perhaps be?
if one uses [a] for the remainder of a, upon division by the integer n (where this remainder is between 0 and n-1, inclusive), we can state this as:
[ab] = [[a]b]. note that [a] is just an integer.
this can be shown using induction on b:
for b = 1:
[a] = [[a]], since 0 ≤ [a] ≤ n-1.
assume that for b = k,
[ak] = [[a]k].
[ak+1] = [(a)(ak)] = [[a][ak]] (see below)
= [[a][[a]k]] (by our inductive hypothesis)
= [[[a]][[a]k]] (by our base case, [a] = [[a]])
= [[a][a]k] (again, see below)
(the crucial step is this:
[[x][y]] = [xy].
note that if x = tn + c, y = un + d, where 0 ≤ c,d < n that:
xy = (tn + c)(un + d) = (tun + c + d)n + cd. writing cd = wn + f, for 0 ≤ f < n, xy = (tun + c + d + w)n + f,
so we have:
[[x][y]] = [cd] = f = [xy]. one can view this as "a rule for brackets and multiplying": remove the outer 2 brackets on each side, and the innermost pair, multiply and add outer brackets).