Modular arithmetic (clock arithmetic) is a system of arithmetic of integers. The basic ingredient is the congruence relation $a \equiv b \bmod n$ which means that $n$ divides $b-a$. In modular arithmetic one can add, subtract, multiply and exponentiate but not divide in general. The Euclidean ...
0
votes
2answers
29 views
Modular arithmetic equation question
i have a general guestion about modular equations:
lets say i have this simple equation:
$$ax=b \pmod{337}$$
I need to solve the equation.
what does "solve the equation mean"? there are an ...
1
vote
1answer
19 views
Related To Polynomial Division
How to prove the following result
Show how a polynomial with odd number of term will never be divisible by a divisor with $x+1$ as factor for modulo $2$ arithmetic.
I don't have any idea.
2
votes
1answer
21 views
Efficient modular exponentation of powers
Is there any way to efficiently compute $(((\mathrm{base}^{M_1})^{M_2})^{M_3} \dots )^{M_n}$ modulo $P$, where $P$ is prime? One way is to repeatedly do modular exponentiation for each of the powers. ...
1
vote
2answers
54 views
Is it true that $a^{k(p-1)+b} \;\stackrel{p}{\equiv} \;\;a^b\;$?
$$a^{k(p-1)+b} \;\stackrel{p}{\equiv} \;\;a^b\;?$$
$p$ prime number and $a,b,k\in\mathbb{N}^+$. And $p$ does not divide $a$.
According to Fermat's Little theorem $a^{p-1}\stackrel{p}{\equiv}1$. So ...
2
votes
1answer
35 views
Congruence Classes in the Guassian Integers?
For some non-zero Gaussian integer n, how can I find a finite upper bound for the number of congruence classes mod n?
0
votes
1answer
29 views
Modulo expansion with divisor multiples
Is there any general expansion for 'a mod mn' ?
mod is modulo operation: http://en.wikipedia.org/wiki/Modulo_operation
...
0
votes
1answer
18 views
Maximum order for $x$ in $g^x \equiv 1 \mod {n}$, when n=pq
I am currently trying to learn about the ElGamal Digital Signature scheme.
It is based on the discrete logarithm problem, where it is computationally infeasible to find $x$ in $y=g^x \mod{p} $), if ...
2
votes
2answers
64 views
What software can calculate the order of $b \mod p$, where $p$ is a large prime?
I wasn't sure where to ask this, but Mathematics seems better than StackOverflow or Programmers.
I have no background whatsoever in number theory, and I need to find software that can calculate the ...
1
vote
2answers
36 views
Show that for any uneven $n$ it follows that $n^2 \equiv 1 \mod 8$ and for uneven primes $p\neq 3$ we have $p^2 \equiv 1\mod 24$.
Show that for any uneven $n$ it follows that $n^2 \equiv 1 \mod 8$ and for uneven primes $p\neq 3$ we have $p^2 \equiv 1\mod 24$.
My workings so far: I proceeded by induction. Obviously $1^2 \equiv 1 ...
3
votes
3answers
39 views
Solving for Modular arithmetic
Solve the equation $38z\equiv 21 \pmod {71}$ for z.
Little confused by the questions. My attempt is: $38 \odot z = 21.$ Then find the inverse of 38 from mod 71 and multiply both sides. Lastly, take ...
1
vote
0answers
39 views
Does there always exist an odd number of elements?
Given a nonzero integer $k$, does there always exist a positive integer $n$ such that there are exactly an odd number of elements $i\in\{0,1,...,n-1\}$ with $\frac{2^n-1}4 < 2^ik \mod{2^n-1} < ...
1
vote
1answer
42 views
$a \mid bc \overset{?}{\implies} \frac{a}{(a,b)} \mid c$
If $a \mid bc$, then does $\frac{a}{(a,b)} \mid c$? I doubt anybody here is industrious enough to show this via a diagram, but who knows.
3
votes
1answer
30 views
Primitve roots and congruences?
Let $p$ be an odd prime. Show that the congruence $x^4$$\equiv -1\text{ (mod }p\text{)}\
$ has a solution if and only if $p$ is of the form $8k+1$.
Here is what I did
Suppose that $x^4$$\equiv ...
-1
votes
5answers
66 views
$(a,m) = (b,m) = 1 \overset{?}{\implies} (ab,m) = 1$
In words, is this saying that since $a$ shares no common prime factors with $m$ and $b$ shares no common prime factors with $m$ too, then of course the product of $a$ and $b$ wouldn't either!?
3
votes
6answers
89 views
$11$ divides $10a + b$ $\Leftrightarrow$ $11$ divides $a − b$
Problem
So, I am to show that $11$ divides $10a + b$ $\Leftrightarrow$ $11$ divides $a − b$.
Attempt
This is a useful proposition given by the book:
Proposition 12. $11$ divides a ...
