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 ...
3
votes
1answer
282 views
Binomial coefficient modulo prime power
I am trying to understand how to find binomial coefficients modulo a power of a prime. I am reading the paper by Andrew Granville for this. But I am unable to understand it completely. More ...
2
votes
2answers
721 views
$n \mid (a^{n}-b^{n}) \ \Longrightarrow$ $n \mid \frac{a^{n}-b^{n}}{a-b}$
How does one prove that if $n \mid (a^{n}-b^{n}) \ \Longrightarrow$ $ \displaystyle n \mid \frac{a^{n}-b^{n}}{a-b}$ where $a,b, n \in \mathbb{N}$.
What i thought of is to consider $$(a-b)^{n} \equiv ...
1
vote
2answers
33 views
Doing modular division when denominator and modulus not coprime
So normally if you calculate $n/d \mod m$, you make sure $d$ and $m$ are coprime and then do $n[d]^{-1}\mod m$ , all $\mod m$. But what if $d$ and $m$ are not coprime? What do you do?
2
votes
0answers
98 views
A system of linear equations in integer squares - solvable?
I consider this more a "recreational math" problem, possibly lacking a solution (because it stems from the question of "magic square of squares") or simply intractable with reasonable effort.
...
0
votes
1answer
97 views
why the increment doesnt affect the randomness?
I'm doing some homework and I need to answer why the increment (b) doesn't affect randomness in the mixed congruential method.
The formula is
$$X_{n+1} \equiv (a X_n + b) \mod m$$
-2
votes
2answers
59 views
Use the modular exponentiation algorithm to find $13^{277} \pmod {645}$
I need to solve this question using the modular exponentiation method.
2
votes
2answers
58 views
Proving if $a_1\equiv b_1\pmod{n}$ and $a_2\equiv b_2\pmod{n}$ then we have $a_1+a_2\equiv b_1+b_2\pmod{n}$.
How can I prove if $a_1\equiv b_1\pmod{n}$ and $a_2\equiv b_2\pmod{n}$ then we have $a_1+a_2\equiv b_1+b_2\pmod{n}$? I have tried several ideas I've found online but don't really understand them. Is ...
1
vote
1answer
25 views
Modulus Cancellation Law
I'm trying to understand the proof for cancellation law in modulus which states that:
...
1
vote
2answers
38 views
Remainders problem
What will be the reminder if $23^{23}+ 15^{23}$ is divided by $19$?
Someone did this way:
$15/19 = -4$ remainder and $23/19 = 4$ remainder So $(-4^{23}) + (4^{23}) =0$ but i didn't understand it
...
3
votes
2answers
44 views
Finding inverse modulo
I'm trying to find "the smallest positive multiple of 100" that leaves remainder 9 when divided by 19.
Here is what I have done before I got stuck:
1) x ≡ 9 mod 19
2) gcd(9,19) = gcd(19,9)
19 ...
0
votes
1answer
30 views
How to maximize $n!\sum^n_{k = 0}\frac{a^k(1+(-1)^{n-k})}{k!(n-k)!} \pmod{a^2}$ for a given $a$?
Short Version of the Question:
How do I maximize the value of $n!\sum^n_{k = 0}\frac{a^k(1+(-1)^{n-k})}{k!(n-k)!} \pmod{a^2}$ for a given $a$?
Long Version of the Question:
I'm currently attempting ...
5
votes
4answers
57 views
$20^{15} + 16^{18}$ is divided by 17
What is the reminder, when $20^{15} + 16^{18}$ is divided by 17.
I'm asking the similar question because I have little confusions in MOD.
If you use mod then please elaborate that for beginner.
...
1
vote
0answers
35 views
Revised: Primes of form $p \equiv m \in S \mod x \ $
Refer to this question for background.
I was speculating if there was an elegant way to define sequences
A007645,A002313,A045357,A045407,A042986,A045331,
A045425,A045374,A045400,A045350,A042988;
...
0
votes
0answers
19 views
Possible to solve a set of congrueces for an unknown divsor?
Recently I started learning about the Chinese remainder theorem and its possibility to solve a set of congruences. Now, for the Chinese remainder theorem you always start from a set of equations from ...
2
votes
2answers
49 views
Can you use modulus to make 0 > 2?
I wanted to create a rock-paper-scissors game that didn't use a lot of conditionals, and I was wondering if there were any mathematical way of representing the cycle of rock-paper-scissors. So Rock ...
4
votes
3answers
321 views
The last 2 digits of $7^{7^{7^7}}$
What is the calculation way to find out the last $2$ digits of $7^{7^{7^7}}$? WolframAlpha shows $...43$.
1
vote
0answers
17 views
Synthetic Division with mods
$x^4+x+1$/
$2x^2$+1
In $F_5$ (means mod 5)
I said let the leading coefficient be 2.
Since $3$ $*$ $2$ - $5$ $*$ $1$ $=$ $1$, choose 3 to multiply
$3$($2x^2$ $+$ $1$)= $x^2$ + $3$ (this is ...
1
vote
1answer
53 views
Does $a \mid bc$ imply $\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.
4
votes
3answers
42 views
Congruences with prime power moduli
I'm trying to figure out the number of solutions to the congruence equation $x^d \equiv1 \pmod{p^2}$ where $p$ is prime and $d\mid p-1$.
For the congruence equation ${x^d}\equiv1 \pmod p$ where $p$ ...
3
votes
2answers
47 views
Existence of a prime
If $x$ is odd and natural and ${x^2}+2\equiv3\mod 4$, how can I show there exists a prime $p$ such that $p|x^2+2$ and $p\equiv3\mod 4$.
3
votes
4answers
162 views
How do I subtract times?
I have an embarrassingly basic modular arithmetic question. I understand that I can subtract, for example, 1 hour from 10 o'clock to get 9 o'clock, or even 2 hours from 1 o'clock to get 11 o'clock; ...
2
votes
1answer
51 views
Modulo in e-voting paper is wrong?
I am trying to run in my mind the registration phase that exists in the paper: Internet Voting Protocol Based on Improved Implicit Security (pdf).
I have chosen as parameters the following:
the ...
3
votes
1answer
33 views
$\mathbb{Z}/m\mathbb{Z}$: A Complete Set of Representatives
So, I'm letting ${\scr{A}}=\{a_1,\dots,a_n\}$ be a complete set of representatives (C.S.R.) for $\mathbb{Z}/m\mathbb{Z}$. I'm considering all $b\in \mathbb{Z}$ and seeing if ${\scr{B}}=\{a_1+b, a_2+b, ...
1
vote
1answer
26 views
Computing $a^r \bmod n$ for a real number $r < 1$
I would like to calculate $d^{1/x} \bmod n$ where $d$ and $x$ belong to $\Bbb Z_n$. Here $x$ is greater than one, thus $1/x$ is less than one. How can I do a computation like that? For example what is ...
5
votes
2answers
164 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
4answers
59 views
$[4]_{17}[x]_{17} = [2]_{17}$: How to optimally solve this equality.
This notation is found in Concrete Introduction to Higher Algebra.
Here is my method:
For something like $[3]_{11}[x]_{11}^2=[4]_{11}$ I've just been using C++ code like this:
...
3
votes
1answer
63 views
How do you calculate $25^{11} \pmod{341}$?
How do you calculate $25^{11} \pmod{341}$?
I understand you have to split the exponent into $11 = 1 + 2 + 8$?
0
votes
2answers
31 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 ...
0
votes
2answers
60 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
46 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
33 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
...
2
votes
1answer
26 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
26 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. ...
2
votes
0answers
75 views
Multiplication structure for finite abelian rings of order $p^2$.
Consider an odd prime $p$ and a positive integer $a$ as close to 2 as possible that is not a quadratic residue $mod$ $p$.
If we extend the ring $mod$ $p$ with the element $b = a^{\frac{1}{2}}$ then ...
0
votes
1answer
19 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
72 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
40 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
43 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
4answers
410 views
solve $100x - 23y = -19$
I need help with this equation $$100x - 23y = -19.$$ When I plug this into Wolfram|Alpha, one of the integer solutions is $x = 23n + 12$ where $n$ is a subset of all the integers, but I can't seem to ...
3
votes
6answers
95 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 ...
-1
votes
5answers
69 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!?
1
vote
2answers
34 views
Determine number of squares in progressively decreasing size that can be carved out of a rectangle
How many squares in progressively decreasing size can be created from a rectangle of dimension $a\;X\;b$
For example, consider a rectangle of dimension $3\;X\;8$
As you can see, the biggest square ...
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
vote
1answer
68 views
Finding a primitive root modulo $11^2$
Find a primitive root modulo each of the following moduli:
a) $11^2$
My TA said he is not going to go over this so do not worry about it. He said you can try this if you want but he would ...
-2
votes
1answer
64 views
Finding a primitive root modulo $13$ [duplicate]
Find a primitive root modulo each of the following integers.
a) $13$
My TA said we are not going to go over this. We did not go over the topic. It seems like something good to know though.
...
2
votes
6answers
96 views
Finding the remainder when $2^{100}+3^{100}+4^{100}+5^{100}$ is divided by $7$
Find the remainder when $2^{100}+3^{100}+4^{100}+5^{100}$ is divided by $7$.
Please brief about the concept behind this to solve such problems. Thanks.
-1
votes
4answers
74 views
One Number in the Set $\{0,1,…,m−1\}$
Let $m$ be a natural number $>1$. Every natural number is congruent modulo $m$ to exactly one number in the set $\{0,1,...,m−1\}$.
Where can I find a concrete proof of this theorem?
1
vote
1answer
28 views
Formula for working out an ID number by given set of coordinates
I'm designing an online game and having a bit of a mental block coding the navigation system. It's designed on a 2 dimensional grid, each cell has an ID 0...n, n being the total number of cells in the ...
5
votes
5answers
250 views
How to solve $100x +19 =0 \pmod{23}$
How to solve $100x +19 =0 \pmod{23}$, which is $100x=-19 \pmod{23}$ ?
In general I want to know how to solve $ax=b \pmod{c}$.
-4
votes
1answer
41 views
least non-negative residue of $a^{67}$ modulo $7$
My professor might accept C++ code to show that for $0 ≤ a ≤ 6$, the least non-negative residue of $a^{67}$ modulo $7$ is $a$.
