Modular arithmetic (clock arithmetic) is a system of integer arithmetic based on the congruence relation $a \equiv b \pmod{n}$ which means that $n$ divides $b-a$.

learn more… | top users | synonyms

2
votes
5answers
1k 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
96 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
110 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
49 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
154 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
122 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
77 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
99 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 ...
1
vote
1answer
437 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
40 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
327 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
88 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
76 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
181 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
438 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
199 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
111 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
69 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
154 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
92 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
89 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
253 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
66 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
61 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
343 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 ...
1
vote
3answers
407 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
275 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
60 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
62 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$?
1
vote
1answer
307 views

Effective formula for the Chinese Remainder Theorem

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
90 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
301 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
86 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
3k 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
44 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
129 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
124 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
239 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, ...
44
votes
8answers
3k views

The last digit of $2^{2006}$

My 13 year old son was asked this question in a maths challenge. He correctly guessed 4 on the assumption that the answer was likely to be the last digit of $2^6$. However is there a better ...
1
vote
0answers
130 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
118 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
152 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
229 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
120 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
76 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 ...
3
votes
1answer
53 views

When does a solution to $a^x\equiv b\pmod m$ exist, and how is the smallest solution denoted?

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
255 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
99 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 ...
1
vote
1answer
184 views

Modular arithmetic word problem

We are buying a total of 12 fruits (apples and bananas) for 132 dollars. If the apples are 3 dollars more expensive than the bananas, and we bought more apples than bananas, how many bananas we ...
6
votes
6answers
135 views

Number Theory and Congruency

I have the following problem: $$2x+7=3 \pmod{17}$$ I know HOW to do this problem. It's as follows: $$2x=3-7\\ x=-2\equiv 15\pmod{17}$$ But I have no idea WHY I'm doing that. I don't really even ...