25 lines
1.8 KiB
Plaintext
25 lines
1.8 KiB
Plaintext
'''[[wp:Modular arithmetic|Modular arithmetic]]''' is a form of arithmetic (a calculation technique involving the concepts of addition and multiplication) which is done on numbers with a defined [[wp:equivalence relation|equivalence relation]] called ''congruence''.
|
|
|
|
For any positive integer <math>p</math> called the ''congruence modulus'',
|
|
two numbers <math>a</math> and <math>b</math> are said to be ''congruent modulo p'' whenever there exists an integer <math>k</math> such that:
|
|
:<math>a = b + k\,p</math>
|
|
|
|
The corresponding set of [[wp:equivalence class|equivalence class]]es forms a [[wp:ring (mathematics)|ring]] denoted <math>\frac{\Z}{p\Z}</math>. When p is a prime number, this ring becomes a [[wp:field (mathematics)|field]] denoted <math>\mathbb{F}_p</math>, but you won't have to implement the [[wp:multiplicative inverse|multiplicative inverse]] for this task.
|
|
|
|
Addition and multiplication on this ring have the same algebraic structure as in usual arithmetic, so that a function such as a polynomial expression could receive a ring element as argument and give a consistent result.
|
|
|
|
The purpose of this task is to show, if your programming language allows it,
|
|
how to redefine operators so that they can be used transparently on modular integers.
|
|
You can do it either by using a dedicated library, or by implementing your own class.
|
|
|
|
You will use the following function for demonstration:
|
|
:<math>f(x) = x^{100} + x + 1</math>
|
|
You will use <math>13</math> as the congruence modulus and you will compute <math>f(10)</math>.
|
|
|
|
It is important that the function <math>f</math> is agnostic about whether or not its argument is modular; it should behave the same way with normal and modular integers.
|
|
In other words, the function is an algebraic expression that could be used with any ring, not just integers.
|
|
<br><br>
|
|
;Related tasks:
|
|
[[Modular exponentiation]]
|
|
<br><br>
|