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

7
votes
3answers
476 views

Number of integers not divisible by $p$ and $q$

Here's a part of question from Siklos' "Advanced Problems in Core Mathematics": How many integers greater than or equal to zero and less than 1000 are not divisible by 2 or 5? What is the average ...
1
vote
2answers
242 views

Power computation in modulo

I have a confusion regarding power computation in modular arithmetic Lets say I want to compute $(7^5)^4 \pmod {17}$ there are many ways to compute this and I get different answers with each ...
5
votes
1answer
250 views

Rotation $x \to x+a \pmod 1$ of the circle is Ergodic if and only if $a$ is irrational

I have a book, Ergodic problems of classical mechanics by Arnold/Avez, and in it they prove that rotation $Tx = x+a \pmod 1$ of the circle $M=\{x \pmod 1\}$ is Ergodic if and only if a is irrational. ...
3
votes
3answers
213 views

Recovering a number from a remainder list

Consider the following list of equations: $$\begin{align*} x \bmod 2 &= 1\\ x \bmod 3 &= 1\\ x \bmod 5 &= 3 \end{align*}$$ How many equations like this do you need to write in order to ...
4
votes
2answers
724 views

Prove that $x^{2} \equiv -1$ (mod $p$) has no solutions if prime $p \equiv 3\pmod 4$.

Assume: $p$ is a prime that satisfies $p \equiv 3 \pmod 4$ Show: $x^{2} \equiv -1 \pmod p$ has no solutions $\forall x \in \mathbb{Z}$. I know this problem has something to do with Fermat's Little ...
1
vote
1answer
134 views

Using modular arithmetic, how can one quickly find the natural number n for which $n^5 = 27^5 + 84^5 + 110^5 + 133^5$?

Using modular arithmetic, how can one quickly find the natural number n for which $n^5 = 27^5 + 84^5 + 110^5 + 133^5$? I tried factoring individual components out, but it seemed really tedious.
3
votes
2answers
103 views

Is there a way to simplify this expression $(a + b) \% c$

I am having an expression of the form $ (a+b) \% c $ where a,b,c are positive integers greater than or equal to zero (natural numbers). $\%$ indicates modulo operation. Also, there is a restriction ...
0
votes
2answers
352 views

Solving an inequality modulo 1

In essence, my problem boils down to finding all $i$ that satisfies this inequality ($n$ is constant): $$ \frac{n}{i} \text{ (mod 1) } < \frac{n}{i+1} \text{ (mod 1) for }n,i\in\mathbb{N}, i < ...
1
vote
2answers
216 views

Proof of equation in modular arithmetic

Can anybody prove that the following equation is true? $$7^n + 9^n \equiv 0 \pmod {11}\quad\text{where}\quad n\equiv 5 \pmod{10}$$ Thanks in advance.
0
votes
2answers
144 views

Compute the square root of $2$ in $R=\mathbb{Z}/n\mathbb{Z}$ where $n=2^s+1$ and $s=2^k$

I have an exam tomorrow and this was on one of the assignment sheets, I couldn't do it then and still can't! Compute the square root of $2$ in $R=\mathbb{Z}/n\mathbb{Z}$ where $n=2^s+1$ and ...
0
votes
1answer
92 views

Proof of modular equivalence?

Let $p$ be any prime number, let $a$ be any number coprime to $p$, and let $x$ and $y$ be random integers. $ax ≡ ay \pmod{p}$ $⇒ay = ax+qp$ $⇒a(y-x) = qp$ Since $a$ divides the left operand, it ...
1
vote
2answers
211 views

Proof prime numbers can't have non-trivial roots?

$a^2 = 1\pmod{p}$ Could someone prove if $p$ is a prime number, $a$ can't be nontrivial?
0
votes
1answer
409 views

Accuracy of Fermat's Little Theorem?

If $a^{N-1} \neq 1\pmod{N}$ for some $a$ relatively prime to $N$, then must the equality fail for at least half the choices of $a<N$ Could someone provide proof for this statement?
1
vote
3answers
100 views

Question on modular arithmetic?

Would this ever be possible: $$a b^2 ≡ a \pmod p$$ where $p$ is a prime number and $1<a<p$ and $1<b$ Please back your answer with some kind of proof other than Fermat's Little Theorem. This ...
3
votes
2answers
320 views

Carmichael numbers?

$a^{p-1} \equiv 1 \pmod p$ Why do Carmichael numbers prevent Fermat's Little Theorem from being a guaranteed test of primality? Fermat' Little theorem works for any $a$ such that $1≤a\lt p$, where ...
1
vote
2answers
117 views

Solutions to $x_1+2x_2+3x_3+4x_4+5x_5+6x_6+7x_7+8x_8+9x_9+10x_{10}\equiv0\mod11$

How many solutions does the following equation have: $x_1+2x_2+3x_3+4x_4+5x_5+6x_6+7x_7+8x_8+9x_9+10x_{10}\equiv0\mod11$ where $x_{1...9} \in \{0,1,2,3,4\ ...\ 8,9\}$ and $x_{10}\in\{0,1,2,3,4\ ...
1
vote
3answers
299 views

Reducing powers in modulo arithmetic

I am working through a modulo tutorial and have become stuck here: $$ 11^{32}(\operatorname{mod}13) = (11^{16})^2(\operatorname{mod}13)= 3^2(\operatorname{mod}13)= 9(\operatorname{mod}13) $$ My ...
4
votes
4answers
161 views

Proof of equivalence?

How do I prove that if two numbers $a$ and $N$ are co-prime, then in the equation: $$ax ≡ ay \pmod N$$ necessarily $x ≡ y \pmod N$
4
votes
2answers
431 views

Fallacy in Fermat's Little Theorem?

Fermat's Little Theorem: If $p$ is prime, then for every $1 ≤ a < p$, $a^{p-1} ≡ 1$ $(mod$ $p)$ Let $p$ be 9 (a composite number), and let $a$ be 2. Let $S$ be the nonzero integers modulo $9$ $S ...
3
votes
4answers
2k views

Multiplicative Inverse?

The book I'm reading defines the multiplicative inverse of $a\pmod N$ as $x$, such that $ax \equiv 1\pmod N$. It then states not all numbers have a multiplicative inverse, such as $2 \pmod 6$. It ...
0
votes
2answers
227 views

Algorithms for solving the discrete logarithm $a^x \equiv b\pmod{n}$ when $\gcd(a,n) \neq 1$

The general discrete logarithm problem is to find $x$ given $a, b$ and $n$ such that $$a^x \equiv b\pmod{n}.$$ Normally one can use the "baby-steps giant-steps" algorithm to solve it fairly quickly. ...
0
votes
1answer
56 views

Addressing a*a mod m overflow problem where m is large

is there another way to calculate a*a mod m mathematically? m is larger than a so (a%m)*(a%m) %m doesn't do anything, but a*a is large enough to overflow.
2
votes
1answer
442 views

Existence of solution of a modular system of linear equations

I want to know if a given system of linear integer equations has an integer solution. I know it is the case if and only if it has a solution modulo $n$ for all integer $n$. What I do not know is when ...
1
vote
2answers
262 views

What is the meaning of symmetric modulo?

So I was reading this: http://rjlipton.wordpress.com/2009/04/01/a-new-factoring-algorithm/ and found it saying "symmetic modulo" So first off: what is " a -special matrix provided the following ...
2
votes
4answers
857 views

Checking if a set is closed under modular multiplication

I have to check if the set {1, 3, 7, 9, 11, 13, 17, 19} forms a group under multiplication modulo 20, and the only idea that I've had so far is: attempt brute force on all the elements (multiplying ...
3
votes
6answers
497 views

Why is the sum modulo n of elements in $\mathbb{Z}_n^*$ equal to 0?

I'm talking about the set $$\mathbb{Z}_n^* = \{x \in \mathbb{Z}_n : \text{gcd}(x,n)=1\}$$ I noticed that for $n>2$, if you add all the elements in the set, you get $0\mod{n}$. Can someone explain ...
21
votes
2answers
24k views

Finding a primitive root of a prime number

How would you find a primitive root of a prime number such as 761? How do you pick the primitive roots to test? Randomly? Thanks
1
vote
0answers
115 views

Generalizing a result on sums involving Euler's function

Motivation: It's known that there is a constant $0<K$ such that for any natural number $N$, $KN\leq \frac{\varphi(1)}{1}+\frac{\varphi(2)}{2}+\cdots+\frac{\varphi(N)}{N}$ (with $\varphi$ being ...
4
votes
1answer
464 views

On sums involving Euler's totient function

I've been struggling with the following claim without being able to prove it, so your help would be highly appreciated: Let $\varphi(n)$ be Euler's totient function. Show that there is a constant ...
3
votes
3answers
172 views

Modular Power equation

I have an interesting problem I solved a while ago, and I was wondering if anyone had a different solution. Let p and q be twin prime integers. Prove that $p^p+q^q\equiv 0 \pmod{p+q}$ I came up ...
4
votes
3answers
259 views

Is it mathematically correct to write $a \mod n \equiv b$?

This is not a technical question, but a question on whether we can use a particular notation while doing modular arithmetic. We write $a \equiv b \mod n$, but is it right to write $a \mod n \equiv ...
1
vote
3answers
1k views

Modular exponentiation?

I came upon an interesting way to relatively quickly compute modular exponentiation with large numbers. However, I do not fully understand it and was hoping for a better explanation. The method ...
2
votes
4answers
239 views

Modular arithmetic and equivalence classes

I completely understand the concept of modulus arithmetic and grasp all the main ideas. The only thing I don’t understand is equivalence classes. The formal definition is: Another interpretation ...
1
vote
4answers
273 views

Find the identity under a given binary operation

I have two problems quite similar. The first: In $\mathbb{Z}_8$ find the identity of the following commutative operation: ...
0
votes
2answers
134 views

modular arithmetic question

know some rules for modular arithmetic expressions, for example, $A+B=C\implies ((A\bmod M) + (B\bmod M))\bmod M = C\bmod M$. 2.$A\times B=C\implies $((A\bmod M)\times (B\bmod M))\bmod M = ...
2
votes
0answers
83 views

When does $n^2$ divide $2^n+1$? [duplicate]

Possible Duplicate: How many rationals of the form $\large \frac{2^n+1}{n^2}$ are integers? A friend of mine asked me this question over lunch, and it's been a week that I can't do ...
3
votes
3answers
115 views

Find inverse of $[-2] \bmod 5$

Given the equation: $$42x\equiv 1\pmod 5$$ I have determined the class $[-2]_{5}$ as $x$ solution of the given equation. Now I have to find the inverse of $x$ (i.e. $x^{-1}=[-2]_5^{-1}$ ). As far as I ...
1
vote
3answers
2k views

How to determine all the invertible elements?

I have this excercise, I need your help on the third point: i) Determine two integers $\alpha$ and $\beta$ such that $12\alpha + 7\beta = 1$ Answer: $\alpha = 3$ and $\beta = -5$ ii) Determine all ...
1
vote
1answer
491 views

RSA Decryption of a huge cipher text and exponent

I am trying to work an assignment question I have been stuck on for some time. The question is to decrypt the message with given decryption key and mod $n$. $$374484638351^{320986308343} \bmod ...
8
votes
4answers
273 views

A solution to $y^5 \equiv 2\pmod{251} $

I need to show that the following equation has a solution. (I am not asked for the answer, which I know by Mathematica to be $y=43$. ) $y^5 \equiv 2 \pmod{251}. $ I know that the order of 2 is 50, ...
0
votes
1answer
59 views

If $m\in\Bbb{Z}_n$ and $q\in\Bbb{Z}_n$, show that $(m + q) \bmod n$ uniquely determines $q$.

Suppose $m$ belongs to $\Bbb{Z}_n$ and $q$ belongs to $\Bbb{Z}_n$, show $q$ in $c=(m + q) \bmod n$ is unique. i.e. Suppose you are given $m$ and $c$, show that $q$ is unique.
1
vote
2answers
126 views

In modular arithmetic is the concept of “increasing” well defined?

If there is a function $f(x) = x\bmod n$ and, whenever $0\leq x_1\lt x_2\lt n$, we have $f(x_1)\lt f(x_2)$, can we say that $f$ is increasing? Also, when finally I prove that $f(x)$ is increasing, ...
2
votes
3answers
143 views

A bunch of questions on $\mathbb{Z}_n$

I'm studying the remainder class $\mathbb{Z}_n$, I've grabbed something, but something else is unfocused. Let $$20x \equiv 4\pmod{34}$$ then GCD(20,34)=2 so I rewrite as: $$10x \equiv 2\pmod{17}$$ ...
1
vote
2answers
162 views

Modular Arithmetic and Congruences

I understand that $a \equiv b \pmod n$ means when you divide each $a$ and $b$ by $n$ you get the same remainder. But why do people say: "$a$ divided by $n$ gives you remainder $b$"? They say that ...
1
vote
1answer
119 views

What are all pairs $(a,b)$ such that if $Ax+By \equiv 0 \pmod n$ then we can conclude $ax+by = 0 \pmod n$?

All these are good pairs: $$(0, 0), (A, B), (2A, 2B), (3A, 3B), \ldots \pmod{n}$$ But are there any other pairs? actually it was a programming problem with $A,B,n \leq 10000$ but it seems to have a ...
0
votes
2answers
340 views

Modular Arithmetic Calendars

If a calendar has 427 days in the year and 8 days a week and the first day of their current year, which is 1027 falls on the second day of their week. What day of the week will the first day of the ...
0
votes
3answers
2k views

How to calclulate multiplicative inverse of e mod $\phi(n)$?

In this wikipedia article about RSA, At step 5, How are they calclulating value of $d$? Can anybody give me a step-by-step explanation? Compute $d$, the modular multiplicative inverse of $e ...
0
votes
2answers
101 views

modular cipher proof

the above is a textbook question I found and believe it is very similar to what I have except n=1 mod p-1 and that remainder 1 is something I dont have in my question... I am terrible at proofs but ...
2
votes
1answer
412 views

Question about finding the nth root in a modulus.

Some notation: $\mathbb Z_n$ denotes the set of integers up to n i.e. $\mathbb Z_n=\{i│i ∈ \mathbb Z,0≤i < n \}$. $\mathbb Z_n^*$ denotes invertible elements of $\mathbb Z_n$ i.e. $\mathbb ...
2
votes
2answers
93 views

Proof that $ (a)^n \bmod n^2 = (a \bmod n)^n \bmod n^2$

Proof that $ (a)^n \bmod n^2 = (a \bmod n)^n \bmod n^2$ I did try a couple of examples and they do seem to work, but I just can't get why it works.