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

1
vote
1answer
133 views

Quick algorithm to compute the order mod m for an element from quadratic field?

For $a+b\sqrt{q}$,where a, b, q are integers and q is square-free, what's the quick algorithm to find the minimal integer n that $(a+b\sqrt{q})^n=1\pmod{m}$? P.S. ...
2
votes
1answer
83 views

Are algebraic properties consistent among ALL types of number groups?

I'm embarking on a self study course of group theory, modular arithmetic, and other mathematics relating to cryptography. I notice that when studying modular arithmetic that they explicitly say that ...
1
vote
2answers
51 views

Proving that if $ed ≡ 1 \pmod{\frac12 φ(n)} $, then $y^{ed} ≡ y \pmod{ n}.$

This is actually the third step of the problem. It's preceded by these questions that I'm sure are supposed to lead me to solution. $n = pq$, p and q distinct odd primes First I'm supposed to show ...
1
vote
3answers
334 views

RSA encryption without a calculator

I'm doing an RSA encryption and to get part of the solution I need to solve $$C=18^{17} \pmod{55}$$ How would I solve this problem without a calculator Thanks in advance
4
votes
2answers
132 views

Twin prime “test” via congruence

I decided to try getting a test for a "twinness" of a prime via Wilson's theorem. Wilson's theorem says that integer $n > 1$ is a prime iff $$(n-1)! \ \equiv -1 \pmod n $$ Now, if both $n$ and ...
-1
votes
1answer
91 views

What is the last digit of $7^{1000}$? [closed]

Someone showed me this question in an linear algebra hw dealing with fields: What is the last digit of $7^{1000}$? What's the idea behind this? Thanks.
2
votes
2answers
96 views

Showing that a system of Diophantine equations will have irrational solutions as well as integers

Solve $\begin{cases} 3xy-2y^2=-2\\ 9x^2+4y^2=10 \end{cases}$ Rearranging the 2nd equation to $x^2=\dfrac{10-4y^2}{9} \Longrightarrow 0\leq x^2 \leq 1$ if $x^2=1$ than $y=\pm\dfrac{1}{2}$ and ...
2
votes
1answer
173 views

Finding the smallest positive integer $ n $ satisfying a modular identity.

Is there any good way of finding the smallest positive integer $ n $ such that $$ 3^{n} \equiv 1 \pmod{1000000007}? $$
0
votes
4answers
74 views

Solve for x: $bx \equiv a \pmod p$

I am trying to solve $bx \equiv a \pmod p$ Where a,b,p is known and p is a prime. For example: $14x \equiv 1 \pmod p \implies x = 4$ Is there an efficient algorithm to solve this equivalance? I ...
1
vote
0answers
72 views

Finding $x^{k}\mod n$ quickly- find algorithm using $x^{2l}=x^{l} \cdot x^{l}$ and $x^{2l+1}=x \cdot x^{2l}$

Finding $x^{k}\mod n$ quickly- find algorithm using $x^{2l}=x^{l} \cdot x^{l}$ and $x^{2l+1}=x \cdot x^{2l}$. Here's my simple algorithm: We first check if $k=1$ or $k=2l$ or $k=2l+1$ for some $l ...
2
votes
3answers
151 views

Modular arithmetic

How do I prove the following inequality with modular arithmetic? (No use of Fermat's last theorem is allowed.) $$3987^{12} + 4365^{12} \neq 4472^{12}$$
0
votes
2answers
31 views

Modular arithmetic of numbers

let us consider two integers a,b that are co prime to a prime number p Then is there any relation between a%p, b%p and ab%p ? % = modulo operator
0
votes
0answers
75 views

Show that the order of 5 mod $2^k$ is $2^{k-2}$ [duplicate]

I have that $5^{2^{k-2}}\equiv 1 \mod 2^{k}$ but I am unsure how to show that $2^{k-2}$ is the least integer that has this property. I thought perhaps I could show that ...
2
votes
0answers
300 views

How many ring homomorphism are there from $\mathbb{Z} / 12\mathbb{Z}$ to $\mathbb{Z} / 20\mathbb{Z}$? Find the image and kernel of them. [duplicate]

How many ring homomorphism are there from $\mathbb{Z} / 12\mathbb{Z}$ to $\mathbb{Z} / 20\mathbb{Z}$? Find the image and kernel of them. The above is the question, this is my attempt at an ...
1
vote
1answer
452 views

modulus calculations & order of operations

This is a 2 part question. part 1 (negative mod calculations): As part of a larger equation, I have come to a stage where I need to calculate -17 mod 11. By doing it manually I got -6 as the ...
0
votes
1answer
23 views

Find $n$ that satisfies $t\equiv nr\pmod{q}$, if such $n$ exists.

So basicially, given the equation $t\equiv nr\pmod{q}$ where $t,r\in\mathbb{N_0}$ and $n, q\in\mathbb{N}$ find $n$ if the rest of the variables are defined. I've figured out a way to see if there is ...
1
vote
1answer
51 views

A First Order Definition of the Mod Function

Is there a good FOL definition of a $\bmod$ predicate in the language of Peano arithmetic? I tried $M(x,n,r) \equiv Ey(x=ny+r)$ but I don't like it very much.
1
vote
2answers
55 views

Find a positive integer $x$ less than $105$ satisfying the following simultaneous congruence equations.

$$x=2 mod 3$$ $$x=3 mod 5$$ $$x=4 mod 7$$ I have only learnt modulo for 2 weeks so far... really basic theorems. My attempt using definitions of modulo From Equation 1, $3a=x-2 ...
2
votes
3answers
92 views

Why is zero mod zero undefined?

Why is zero mod zero undefined? To me, the answer must be zero, because $0 \times N + M = 0$ has only one solution for $M$, zero. (Assuming $M$ and $N$ are integers.) However, today I found out that ...
2
votes
2answers
641 views

Prove that $x^3 \equiv x \bmod 6$ for all integers $x$

Prove that $x^3 \equiv x \bmod 6$ for all integers $x$ I think I got it, but is this proof correct? We can write any integer x in the form: $x = 6k, x = 6k + 1, x = 6k + 2, x = 6k + 3, x = 6k + ...
1
vote
1answer
36 views

Solve $r=(p-1)+pr_1+p^2r_2$ for $r_1$ and $r_2$ when $r(p-1) \equiv 1$ (mod $p^3$)

Let $p$ be an odd prime. $\mathbb Z_{p^3}=\left\{0,1,...,p^3-1\right\}$ 1) Let $r$ be an element of $\mathbb Z_{p^3}$. Then, we can define $r$ as follows: $r=(p-1)+pr_1+p^2r_2$ for some $0\leq ...
0
votes
1answer
80 views

Modular equation inverse of itself

What is a^(-1)mod a? From what I've tried it came out to be zero because a^(-1) = a * a^(-2) a^(-1)mod a = a * a^(-2) mod a a * a^(-2) is divided by a so the result should be zero. Is my proof ...
3
votes
4answers
904 views

how do I calculate inverse modulo of a number when the modulus is not prime?

I came through Fermat's Little theorem, and it provides a way to calculate inverse modulo of a number when modulus is a prime. but how do I calculate something like this 37inverse mod 900?
2
votes
1answer
219 views

Modulo operation of large powers

I came through this property in a cryptography book. $(ab)\bmod n=\bigl((a \bmod n)(b \bmod n)\bigr)\bmod n$. There is an example in the book, $10^n\bmod 3= (10\bmod n)^n$. Now if I have ...
0
votes
1answer
258 views

Square root of 5 in modulo prime field

How can we efficiently find square root of 5 in a mod prime field. By quadratic reciprocity we can argue that 5 is a square in modulo p(prime) is p is square modulo 5. But how exactly can we calculate ...
0
votes
1answer
107 views

Modular 2-adic Integers Question

I would like to know if the following statement is true in the 2-adic integers. $\forall n( n=0 \lor Ex( (x \neq 0 \land x+x=0 \bmod n) \lor (x+x=1 \bmod n) ))$ I will define a modulo predicate as: ...
0
votes
1answer
482 views

How to Solve an equation with mod for a variable?

I have following equation to be solved, but I am having some trouble in making an understanding and doing so. (d * e) % v = 1 e and v are known. How to solve this ...
0
votes
1answer
45 views

Explain this Modular Arithmetic Expression in Z[i]

Let $\pi = a+bi$ and $\lambda = c+ di$ be relatively prime in $\mathbb{Z}[i]$. They also said that they were "primary" meaning that $\pi = \lambda = 1 (\text{mod } (1+i)^3)$, though I suspect this is ...
0
votes
3answers
148 views

Why is the group of units mod 8 isomorpic to the Klein 4 group?

I recently learned that $U_8\cong \mathbb Z/2\mathbb Z\oplus \mathbb Z/2\mathbb Z$. I can see, through a bit of computation, that this is the case, but I was wondering if this is just a coincidence ...
1
vote
3answers
182 views

Computing an inverse modulo $25$

Supposed we wish to compute $11^{-1}$ mod $25$. Using the extended Euclid algorithm, we find that $15 \cdot 25 - 34 \cdot 11 =1$. Reducing both sides modulo $25$, we have $-34 \cdot 11 \equiv 1$ mod ...
0
votes
1answer
225 views

Is a congruence (equivalence) class modulo n a group?

I know that the set of all equivalence classes Z/nZ is a group (with identity element the equivalence class [0], inverse element -[a]=[n-a]=[-a], etc.). However, is a single equivalence class modulo ...
4
votes
1answer
273 views

Fast way to find the smallest root $\mod M$ of a polynomial

Suppose you're given a polynomial of degree $d$ with integer coefficients: $$ P(x) = \sum_{i=0}^{d}{a_i x^i} $$ Is there a fast way to find the smallest root modulo $M$, where $M$ is some composite ...
1
vote
2answers
46 views

Linear congruences $2X\equiv9\pmod{26},\pmod{25}$

May double that of a natural number let rest $9$ when divided by $26$? And when divided by $25$? I tried: $$2X\equiv9\pmod{26}$$ As $(26,2)=2$ and $2\nmid9$ then the congruence linear not ...
5
votes
1answer
64 views

Is it true that if $n$ is even then $\sum_{k=1}^{n}(n \bmod k)<\frac{8}{45}n^2$?

Let $f(n,k)$ be the least non-negative integer such that $n\equiv f(n,k) \bmod k.$ $f(10,k)(k=1,2,\cdots,10)=0, 0, 1, 2, 0, 4, 3, 2, 1, 0.$ Hence $$\sum_{k=1}^{10}f(10,k)=1+2+4+3+2+1=13.$$ ...
2
votes
1answer
66 views

How to solve the equation $x^2=a\bmod p^2$

What is the standard approach to solve $x^2=a\bmod p^2$ or more general $x^n = a\bmod p^n$ ?
0
votes
1answer
33 views

Given a set of numbers $x_1, x_2, \ldots, x_k$, what is the largest number $h$ such that $x_i \bmod{h} = 0$ for all $i$?

I am solving a system of differential equations with respect to length, let's say 0 to $x_{max} = 10$ meters. Now, I want to choose an integration step such that my step will land on each of the ...
0
votes
2answers
242 views

find a general expression for the remainder when a prime divides a fibonacci.

I have primes of form $5k\pm1$. Consider the equation: $F_n=f(n)\pmod p$ where $F_n$ is the nth fibonacci number. Now given a c, how can i check whether or not there exists a solution for $f(n)=c ...
1
vote
0answers
516 views

Calculating Pisano periods for any integer

I recently stumbled across this SPOJ question: http://www.spoj.com/problems/PISANO/ The question is simple. Calculate the Pisano period of a number. After I researched my way through the web, I found ...
1
vote
3answers
88 views

Remainder when dividing $3^{10}+3^{10^2}+3^{10^3}+…+3^{10^{100}}$ by $7$

Determine the remainder of dividing $10^{10}+10^{10^2}+10^{10^3}+...+10^{10^{100}}$ by $7$ We have $10\equiv3\pmod7$ then ...
2
votes
1answer
340 views

How to prove algorithm for solving a square congruence when p ≡ 5 (mod 8)

I'm having trouble understanding why this algorithm works and where it comes from: "Suppose p ≡ 5 (mod 8) is a prime and y is a square (mod p); that is, for some $ x, x^2 ≡ y\ (mod\ p)$. This can be ...
5
votes
0answers
323 views

How to solve congruence $x^y = a \pmod p$?

I'm having trouble solving this congruence: $$x^{114} \equiv 13 \pmod {29}.$$ I thought that it made sense to try to solve it using this idea: "Suppose you want to solve the congruence $ x^y \equiv a ...
2
votes
1answer
287 views

Subgroups of $U(n)$ isomorphic to a direct sum of cyclic groups

Let $U(n)$ to be the set of all positive integers less then $n$ and relatively prime to $n$. Then $U(n)$ is a group under multiplication modulo $n$. A. Find integer $n$ such that $U(n)$ contains ...
4
votes
1answer
286 views

Proving that there are n Equivalence Classes Modulo n

For $a,b,n \in \mathbb{Z}$ and $n \geq 2$, I want to prove that there are $n$ equivalence classes mod $n$. I'm not sure how to do it - would I do it inductively? Any help would be appreciated.
12
votes
4answers
3k views

Why is n mod 0 undefined?

I tried to find out what $n$ mod $0$ is, for some $n\in \mathbb{Z}$. Apparently it is an undefined operation - why?
2
votes
1answer
205 views

General Exponential modular equation

Can anyone tell me how to solve this equation for lowest $x$ $$a^x \equiv n \mod m$$ other than trying every possible $x$ from $0$ to $m-1$ ($m$ is prime)?
3
votes
2answers
158 views

Proving divisibility without an inductive proof.

Is there a way to prove that $$10^{n+1} + 10^n + 1$$ is divisible by three without using a proof by induction? We are supposed to use the properties of expressions such as $a$ is congruent to $b \pmod ...
1
vote
2answers
176 views

Extended euclidean algorithm

So I am trying to figure this out. And for one of the problem the question is x*41= 1 (mod 99) And the answer lists ...
0
votes
1answer
34 views

For what $x$ is $\sum_{k=1}^{n-1} (x+k)^n \equiv 0 \pmod n$ dependend on $n$? (so far only *odd* n)

(This is a detail in my attempted answer of this MSE question) We look at $$f_n(x) = \sum_{k=1}^{n-1} (x+k)^n $$ I came to the following observation - for odd $n$ at the moment -, but do not see how ...
0
votes
1answer
29 views

Figuring out a factor of modulo multiplication knowing other factors

So the problem is this - we have a simple equation: (A * B) % N = X All numbers are large integers. We know B, N and X, is it possible for us to figure out the last factor A without checking every ...
3
votes
1answer
34 views

Let $n = 10k + d$ where $d$ is the last digit of $n$. Show that $23|n$ if and only if $23|(2d-3k)$.

This is an exercise on my text book that i don't know how to prove it. Let $n = 10k + d$ where $d$ is the last digit of $n$. Show that $23|n$ if and only if $23|(2d-3k)$.