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
34 views

How come when $2^{k} | (x-1)(x+1)$ one of the terms is divisible by $2$ and not by $4$ when $k \in \mathbb{N} $ and $3 \leq k$

So I'm reading Knuth's 'Discrete Mathematics' at the moment and there's a paragraph detailing how many solutions are there for $x^{2} \equiv 1 \pmod{p}$. So other cases (when $p$ is an odd prime or ...
0
votes
1answer
38 views

Question about $a \equiv b \pmod{mn} \Leftrightarrow a \equiv b \pmod{m} \wedge a \equiv b \pmod{n}$

So Knuth's 'Discrete Mathematics' states that: $a \equiv b \pmod{mn} \Leftrightarrow a \equiv b \pmod{m} \wedge a \equiv b \pmod{n}$ if $m$ and $n$ are relatively prime. But being a curious human ...
4
votes
2answers
76 views

Smallest such $n \in \mathbb{N}$ that $2^{n} \equiv 1 \pmod{5\cdot 7\cdot 9\cdot 11\cdot 13}$

Can anybody give me a hint about how to find smallest such $n \in \mathbb{N}$ that $2^{n} \equiv 1 \pmod{5\cdot 7\cdot 9\cdot 11\cdot 13}$? I thought that I will find it piece by piece with help ...
1
vote
0answers
26 views

Finding the totient functionlike function for an irrational number like (a+b*sqrt(5)) where a and b are whole numbers mod M where M is a whole number.

I need to find if a value $T$ exists for irrational number of the form $(a+b\cdot \sqrt{5})$ such that $(a+b\cdot \sqrt{5})^T = 1 \pmod M$. Also ,is it possible to find out upper bound for T .
1
vote
1answer
51 views

A curious congruence relation

Find the set of values for n such that $x^n \equiv{x}\mod 10$, where $n, x\in\mathbb{N}$. This question looks like a Fermat's little theorem question but $10$ is not prime. Rather the smallest ...
2
votes
1answer
90 views

Proof using Chinese Remainder Theorem for $n=p_1^{m_1}\cdot p_2^{m_2}\cdots p_k^{m_k}$

I wish to find an expression for the number of solutions $x$ to $x^2\equiv 9 \pmod n$, with $x$ a natural number${}<n$, when $n$ has a factorization $n=p_1^{m_1}\cdot p_2^{m_2}\cdots p_k^{m_k}$ ...
0
votes
1answer
362 views

What will be the multiplicative inverse of square root of 5 with respect to a natural number $M$?

Can such a number $N$ be found such that $\sqrt{5}N \equiv 1 \mod M$? If no,what can be the best approximation for $N$?
0
votes
2answers
363 views

What is a perfect square in mod n

I have been stuck with a question on eliptic curves lately. I need to know whether perfect square mod n is different than a normal perfect square. And also is 3 a perfect square in mod 13?
1
vote
1answer
113 views

Prove that there exists only 2 solutions for $x^2 \equiv 9 \pmod {p^k}$, ($p$ an odd prime > 3 and $x$ a natural number < $n$)

It appears that the only two solutions are always $3$ and $p^k-3$, I want to prove this, here has been my approach, I think I am close but just missing something, would really appreciate any help!!! ...
0
votes
1answer
53 views

Prove that for $n=2^k$, $(k \ge 3)$ there are 4 natural numbers less than $n$ that satisfy $b^2 \equiv 9 \pmod n$.

I think I am close to proving this, but just need a bit of help with some gaps in my understanding. I found using a recursive function in a small program that it seemed that for $k \ge 3$, I always ...
2
votes
1answer
96 views

Number of points on $Y^2 = X^3 + A$ over $\mathbb{F}_p$

Let $p\equiv 2\pmod{3}$ be prime and let $A\in\mathbb{F}^{∗}_p$ . Show that the number of points (including the point at infinity) on the curve $Y^2 = X^ 3 + A$ over $\mathbb{F}_ p$ is exactly $p + 1$ ...
0
votes
5answers
3k views

How often in years do calendars repeat with the same day-date combinations (Julian calendar)?

E.g. I'm using this formulas for calculating day of week (Julian calendar): \begin{align} a & = \left\lfloor\frac{14 - \text{month}}{12}\right\rfloor\\ y & = \text{year} + 4800 - a \\ m & ...
3
votes
1answer
47 views

modular arithmetic with large numbers

I am having trouble finding a number where 579^$65$ is congruent to x mod 679 and x has to be less than 676. i did the trick of 2's and got: $579^2$ $\equiv$ 494 mod 679 $494^2$ $\equiv$ 275 mod 679 ...
1
vote
2answers
75 views

modular arithmetic with a very big number

I need to compute $147^{65}\pmod{679}$. I need to get it to be congruent to a number less than $676\pmod{679}$. Anyone who can help? I tried the power of $2$ trick but I couldn't make it work.
0
votes
1answer
47 views

Modular Exponentiation Equivalence Problem

Find the integer $a$ such that $0 \leq a < 113$ and $102^{70} + 1 \equiv a^{37} \bmod{113}$. I started off by using modular exponentiation to realize that the left side of the congruence is ...
2
votes
3answers
64 views

computing $2^{170}+ 3^{63}\pmod {19}, 3^{175} + 2^{73} \pmod {17}$, etc… by hand

I came across several questions like this in the problem section of a book on coding theory & cryptography and I have no idea how to tackle them. There must be a certain trick that allows for ...
0
votes
2answers
123 views

Finding $x$ that make $x^2 ≡ 1 (\mathrm{mod} \ n)$, when $n$ is a composite number

How do I find $x$, $( x > 1)$, that makes $x^2≡1 (\mathrm{mod} \ n)$, for any natural number $n$?
1
vote
1answer
108 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
79 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
48 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
260 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
106 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
87 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
89 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
163 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
69 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
71 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
135 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
27 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
69 views

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

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
286 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.

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
275 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
21 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
45 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
54 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
81 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 ...
1
vote
2answers
506 views

'prove that $x^3 = x mod 6$ for all $x$ in the set of integers' 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 + 4$, and $x = 6k + 5$. If $x = 6k$, then $x^3 = 216k^3$. Then $x^3 - x = 216k^3 - 6k = 6(36k^3 - k)$. ...
1
vote
1answer
35 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
67 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
592 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
144 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
206 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
323 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
43 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
136 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
126 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
168 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
192 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 ...