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 ...
2
votes
5answers
50 views
Showing $na \equiv 1 \pmod m$ and $n'a \equiv 1 \pmod m \implies n \equiv n' \pmod m$ for $(a,m) = 1$
We have $(a,m) = 1$ iff exists integer $n$ such that $na \equiv 1 \pmod m$. Prove $na \equiv 1 \pmod m$ and $n'a \equiv 1 \pmod m$ implies $n \equiv n' \pmod m$.
For this question, I have so far
$na ...
2
votes
1answer
29 views
Modular arithmetic terminology
In division, we have terms like divisor, dividend, quotient, remainder. Do we have like terms for modular arithmetic? In particular, in the following, does $n$ have a special name such as "modulator" ...
2
votes
4answers
79 views
modular arithmetic (number theory)
Assume that $$7^{64} = 1 \mod 120.$$
I am trying to find $$7^{62} \mod 120.$$
In my maths text, I was told that:
$$\begin{align}
7^{62} & = 7^{64} \cdot 7^{-2} \\
& = 7^{-2} \quad \\
&= ...
1
vote
5answers
239 views
prove that $a \equiv b \mod m$ is an equivalence relation on the integers
prove that $a \equiv b \mod m$ is an equivalence relation on the integers
I believe there are 3 properties that it must meet to prove and equivalence relationship. Any reference material would be ...
0
votes
3answers
86 views
Prove that $(a,m) = 1$ iff there exists an integer $n$ such that $na \equiv 1 \pmod m$
Prove that $(a,m)=1$ iff there exists an integer $n$ such that $na \equiv 1 \pmod m$
How do I go about this problem?
2
votes
1answer
85 views
How is this done?
The question here:
A number when successively divided by 9, 11 and 13 ...
I found the answer to it in a book and this was the answer:
...
1
vote
1answer
47 views
Prove that if $[a] + [b] \equiv [a] + [c] \pmod n$, then $[b] \equiv [c] \pmod n$.
The question is very clear that we are dealing with classes. Does that change anything in this case? This was an unsolved example for class and I feel it's unusual that I don't know how to begin.
2
votes
3answers
90 views
high power congruences finding $x$
trying to solve:
$$x^{13} \equiv 11 \pmod{135}$$
I came to the fact that $x = 11^{59}$ but its in mod $72$ and needs to be converted to mod $135$
any suggestions? I'm not sure how to change it to ...
2
votes
3answers
116 views
Proving $4^{47}\equiv 4\pmod{12}$
I know this is a simple exercise, but I was wondering if I can make the following logical jump in my proof:
We see that $4\equiv 4\pmod{12}$ and $4^2\equiv 4\pmod{12}$. Then we can recursively ...
2
votes
1answer
40 views
How does this periodic trig function that calculates modulus work?
$$ \arctan(\tan(( dividend - \frac{divisor}{2}) \times \frac{\pi}{divisor}))*\frac{divisor}{\pi}+\frac{divisor}{2}= dividend \bmod divisor $$
This is a follow up to ...
3
votes
1answer
55 views
Solve the congruence$x^3+4x+8\equiv{0}\pmod{15}$
Solve (if possible)the congruence involving polynomial
$x^3+4x+8\equiv{0}\pmod{15}$
My work:
Since $15=3\cdot5$, we have
$x^3+4x+8\equiv{0}\pmod{3}$ and $x^3+4x+8\equiv{0}\pmod{5}$
In ...
0
votes
1answer
135 views
Solve the congruence $x^3+2x-3\equiv{0}\pmod{45}$
Solve (if possible)the congruence involving polynomial
$x^3+2x-3\equiv{0}\pmod{45}$
My work:
Since $45=3^2\cdot5$, we have
$x^3+2x-3\equiv{0}\mod(3)$ and $x^3+2x-3\equiv{0}\pmod 5$
In ...
2
votes
0answers
33 views
eliminate very kth element in mod n… save a given element for last
we are given 1....n numbers. lets say we are to save a given number element k for last in elimination. We start eliminating them in the following manner.
I eliminate 1 at first. Then eliminate the ...
3
votes
9answers
271 views
Why does a number like $2^n\bmod 7$ have a repeating pattern?
I am struggling with the formal understanding of why a number like $2^n\bmod7$ have a repeating pattern? $1, 2, 4, 1, 2 ,4\ldots$
The repeating pattern show up in many places of modular arithmetic, ...
0
votes
1answer
66 views
Equations With Two Linear Congruences
Is there a known way to isolate a variable when the equation has two linear congruences each containing the variable?
$$200=\left(\frac{x}{4}-(x \mod 17)+\frac{3}{4} \right)\cdot 3 \cdot ...
0
votes
2answers
50 views
Why is it safe to assume M < all Ns in Håstad's Broadcast Attack
I am reading the Wikipedia article on Broadcast attack. In the prove, the editor made an assumption that M is less than all N. Why is this assumption safe?
0
votes
4answers
97 views
Using modular congruence to solve equation
Show that there are no intergers $x$ and $y$ such that
$P(x,y)=x^2-5y^2=2$
Hint from professor:
Consider the equation in a convenient $\mod (n)$ so that you end up with a polynomial in a single ...
1
vote
2answers
118 views
Solving non-linear congruence
$x^2+2x+2\equiv{0}\mod(5)$, $7x\equiv{3}\mod(11)$
My attempt:
$x^2+2x+2\equiv{0}\mod(5)$
$(x+1)^2\equiv-1\mod(5)$, we have $x+1\equiv-1\mod(5)$
since $5$ and $11$ are coprime. We have a solution ...
3
votes
4answers
94 views
Modular arithmetic polynomial question
Is it possible to find all polynomials of the form $ an^2 + bn +c $ where a,b, and c are integers and such that
$$ a+b+c \equiv 31 \pmod{54} $$
$$ 4a+2b+c \equiv 3 \pmod{54} $$
$$ 9a+3b+c ...
2
votes
1answer
42 views
How to build fast exponentation for modular?
I need to find modular value of some big number which I cannot calculate by calculator (i.e $233^{351} \pmod {853}$. How can I build a fast exponentiation table for this?
2
votes
1answer
55 views
How many solutions to prime = $2 b^2 c^2 + 2 c^2 a^2 + 2 a^2 b^2 - a^4 - b^4 - c^4$
Let $a,b,c$ be integers, no sign restriction.
Let $p$ be a given prime.
How to find the number of solutions to $p = 2 b^2 c^2 + 2 c^2 a^2 + 2 a^2 b^2 - a^4 - b^4 - c^4$ ?
Note, from Heron's ...
3
votes
3answers
119 views
How many solutions to prime = $a^3+b^3+c^3 - 3abc$
Let $a,b,c$ be integers.
Let $p$ be a given prime.
How to find the number of solutions to $p = a^3+b^3+c^3 - 3abc$ ?
Another question is ; let $w$ be a positive integer. Let $f(w)$ be the number of ...
1
vote
2answers
71 views
How many solutions to prime = $(d^2-2ad+b^2-2ab+2a^2)(d^2-2cd+2c^2-2bc+b^2)$?
Let $a,b,c,d$ be integers $>-1$.
Let $p$ be a given prime.
How to find the number of solutions to $p = (d^2-2ad+b^2-2ab+2a^2)(d^2-2cd+2c^2-2bc+b^2)$ ?
I assumed that this polynomial above does not ...
-1
votes
1answer
83 views
simplyfying a mathematical expression
How to calculate the value of below expression where $M$ is 1000000007 (prime) and $N$ can be any large number $\le 1000$?
\[\frac{N!}{(N/2)!(N/2)!} \mathbin{\%} M\]
It is possible to simplify it ...
0
votes
3answers
127 views
Computing Large Powers
So this is my question:
Compute $7^{818} \pmod {1637}$ using no more than 14 multiplications mod 1637. (You should of course verify that 1637 is prime if you plan to use Fermat's Theorem.)
I would ...
2
votes
0answers
45 views
How much information do I gain from each modular inequality?
Problem details:
Let $p = 2^{48}$, $s\leftarrow\{0,1\}^{48}$, and $a,b$ known constants.
Furthermore let $f(x) = a x + b \pmod{p}$
and let the value $r_k$ be defined by the first-order recurrence ...
0
votes
0answers
53 views
a question from modular arithmetic
Given $a,b$ in $Z_N$* for some composite positive integer N. Let the bit sizes are $a_N , b_N , N_N$ respectively.
Also $a_N = (N_N$ or $N_N-1) , a<N , (a,N)=1$
$ b_N = (N_N$ or $N_N-1) , ...
1
vote
0answers
139 views
Binomial coefficient modulo prime power without generalized Lucas theorem
I've been working on this problem computing n choose r for large n and r, modulo a composite.
I could implement the generalized lucas theorem to handle the prime power case, but I want to understand ...
1
vote
3answers
101 views
Solving simultaneous linear congruences
(a) $x≡5\pmod 7\;\;,\; x≡7\pmod{11}\;\;,\;\;x≡3\pmod{13}$
(b) $x≡3\pmod{10}\;\;,\;\; x≡8\pmod{15}\;\;,\;\;x≡5\pmod{84}$
for (a) I have a rough idea how to do it, its like:
$n_1=7,n_2=11,n_3=13$ ...
3
votes
2answers
245 views
Conjecture I came up with
For each number translated into binary
$0$, $1$, $10$, $11$, $100$, $101$, $110$, $111$, $1000$, ...
find a number where, when you take the length of the binary number, the binary number and the ...
0
votes
2answers
45 views
System of Linear Equations for Congruency
So this is my question:
Find all x such that $4x=3 \pmod{21}$, $3x=2 \pmod{20},$ and $7x=3 \pmod{19}$
So I know I have to use chinese remainder theorem and I know how to do it if $x$ didn't have a ...
2
votes
1answer
54 views
modular arithmetic : $((a-b)/c)\bmod m = {}$?
How can I express $((a-b)/c) \bmod m$ in terms of $a \bmod m$, $b \bmod m$ and $c \bmod m$?
0
votes
1answer
128 views
Chinese Remainder Theorem in Reverse
By the Chinese Remainder Theorem, we can find three numbers $j$, $k$, and $i$ such that $0 < j < p$, $0 < k < q$, $i \equiv j \pmod p$, $i \equiv k \pmod q$, $p$ and $q$ are prime and $i ...
0
votes
2answers
77 views
Fermat's Little Theorem Transformation
I am reading a document which states:
By Fermat's Little Theorem, $a^{p-1}\bmod p = 1$. Therefore, $a^{b^c}\bmod p = a^{b^c\bmod (p - 1)} \bmod p$
For the life of me, I cannot figure out the logic ...
1
vote
1answer
66 views
Solving a non-linear congruence
How can we solve for $x$, knowing the integer $n$ and the real numbers $a$ and $b$, the following non-linear congruence:
$(x+a)^2=-b\pmod{n}$
Specifically in this example:
...
-1
votes
1answer
56 views
primes of type norm($a+b\sqrt{-c}$) = primes of type $1$ $mod$ $c 2^{n-1}$?
Let $a,b,c,n$ be strictly positive integers where $c$ is a prime and such that the normed ring $a+b\sqrt{-c}$ is a UFD.
I noticed the primes of norm($a+b\sqrt{-1}$) are $1 \bmod 4$. Also the ...
1
vote
3answers
236 views
Finding the last two digits
This is my question:
Find the last 2 digits of $123^{562}$
I don't even understand where to begin on this problem. I know I'm supposed to use Euler's theorem but I have no idea how or why. Any help? ...
0
votes
3answers
42 views
Showing if I choose a set of $10$ unique numbers from $0$ to $14$
How would I show if I choose a set $10$ unique numbers from $0$ to $14$, there exists two numbers in the set such that their sum is greater than the largest number in the set?
3
votes
2answers
93 views
Calculate $20^{1234567} \mod 251$
I need to calculate the following
$$20^{1234567} \mod 251$$
I am struggling with that because $251$ is a prime number, so I can't simplify anything and I don't have a clue how to go on. Moreover how ...
6
votes
1answer
86 views
Tell wether $(1234657)! +1 \equiv_{11111} (7654321)! -1$ is true or false
I have to tell if the following is true or false:
$$(1234657)! +1 \equiv_{11111} (7654321)! -1$$
so by definition we can rewrite the previous equivalence as:
$(1 \cdot 2 \cdot \ldots \cdot 11110 ...
0
votes
1answer
123 views
Quadratic Residues, Non-residues and Primitive Roots
Can anyone explain to me what special significance each of these has. I know how to calculate/verify whether a number is one of them relative to a modulus using Euler's criterion, but, for example, ...
1
vote
0answers
75 views
Residue division algorithm
What is the current state of the art method for determining, the residue of a large integer $k$ modulo $m$?
The only useful idea I can think of, which Ive seen used in base 10, is if $k$ was written ...
0
votes
0answers
81 views
Solving systems of linear congruences with rational coefficients
Is there any way to solve for $x$ in a system of linear congruences with rational coefficients in the following form?
$$Ax \equiv b\pmod 2, \space where\space A \in \Bbb Q^{n,m}, b \in \Bbb Q^m$$
...
1
vote
3answers
100 views
modulo question
What is the value of
$$\large n\pmod {\phi(n)}$$
where $\phi(n)$ is the Euler function, I know that if $n$ prime the this value is $1$, because $\phi(n)=n-1$, but for random natural number this ...
3
votes
1answer
139 views
Modulo of power sum
$$\left(\sum_{k=1}^{2011}k^n\right)\equiv0\mod n$$
Find the all possible value(s) of $n$
I have no idea to start the question
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
0answers
63 views
Floor function within a congruence
In essence, the floor function is causing problems. Is there any way to get the inner linear expression, outside of the floor function?
$\lfloor(a_1x_1+...+a_nx_n)/d\rfloor \equiv b\pmod m$,
for ...
2
votes
1answer
31 views
Congruence help
Given fixed integers $a,b,m$ such that $\gcd(a,m)=1$, how do I know if there exists an integer $x$ such that $a^x\equiv b\text{ mod } m$, also if a solution does exist, what is the typical notation ...
2
votes
1answer
67 views
System of Linear Equations using Mod
I just want to check that I did a certain problem correctly. This is it:
$$a+b=3 \pmod{26}\\2a+b=7 \pmod{26}$$
Solve for $a$ and $b$
Now I setup the augmented matrix:
$$\left[ \begin{array}{ccc}
1 ...
0
votes
2answers
77 views
Finding $a \bmod b$ where $a,b$ are large Fibonacci numbers
For moderately large values of $b$ we can use Chinese Remainder Theorem, by factorizing $b$. But for very large values of $b$, (for example $b$ is the 1000th Fibonacci number) factorization will take ...
