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

3
votes
4answers
59 views

Is this a valid way of solving modular equations?

Some of the exercises in my abstract algebra textbook involve solving congruence equations, for example $$5x \equiv 1 \pmod 6$$ I convert that to a linear equation by rewriting $$x = \frac{k6+1}{5} = ...
5
votes
3answers
108 views

Modulos race, which formula reach 100 first?

I would like to know if there was a way to determine according to this formula: \begin{equation*} \sum_{i=0} \frac{A*i+B \pmod{100}}{100} \end{equation*} and the same with different values of A and B ...
2
votes
1answer
18 views

Sequences formed by integer evaluations of polynomials modulo $ p^{k} $, where $ p $ is a prime number and $ k \in \Bbb{N} $.

I have the following question. Let $ p $ be a prime number and $ k $ a positive integer. Let $ (a_{n})_{n \in \Bbb{Z}} $ be a two-way sequence in $ \Bbb{Z} / p^{k} \Bbb{Z} $. Then is it true that ...
1
vote
1answer
50 views

Solvability of the congruence $(x+a)^n\equiv x^n\pmod p$ in $x$

When thinking about solving the diophantine $x^n-y^n=1001$ I noticed that my knowledge about the prime factorisation of $x^n-y^n$ does not suffice to attack such diophantines in general. Note I'm ...
0
votes
0answers
20 views

Factorization of a number obtained by a modular multiplication operation can reveal factors of the used operands?

Consider a number $r$ obtained by: $r=a⋅b \mod n$ Knowning the factorization of $r$ can reveal some information (bits) of $a$ and $b$ ?
0
votes
1answer
44 views

Prove, if $n>6$ is an even, perfect number, then $n\equiv4 \pmod 6$

I've been working on this for quite awhile, and am stumped after a little bit. I have some stuff written down, but I just don't know how to completely prove it. I don't have much done yet: ...
1
vote
1answer
52 views

how to solve $3x^3\equiv 7\pmod{925}$

I am trying to solve $3x^3\equiv 7\pmod{925}$ I thought using Brute Force but $925$ is too big for that. Also i tried raising both sides of the equation to power of $3$ but it didn't help. How can ...
0
votes
0answers
32 views

Modular arithmetic, specifically n! mod m

Is there a theorem that makes solving $$ n! \equiv x \mod m $$ knowing that both $n$ and $m$ are prime? And if not, what would be the best way to go about finding $x$? cheers
2
votes
4answers
85 views

Prove that $a$ and $a^{-1}$ inverse have the same order in $Z_n$

So there is a question in my lecture notes that I'm not too sure how to approach. It reads as follows: Suppose $a$ is invertible modulo $n$. Prove that $a$ and $a^{-1}$ have the same order in ...
2
votes
1answer
25 views

Distributive modulo?

I would like to know if the modulo operation has distributivity like this: $$A+B+C \pmod{M} = (A+B)\pmod{M} +C \pmod{M}$$? Does the equality hold true?
2
votes
2answers
49 views

Prove that $a^{p^2}\equiv a^p\pmod{p^2}$ for every $a\in\mathbb{Z}$

Question: Prove that $a^{p^2}\equiv a^p\pmod{p^2}$ for every $a\in\mathbb{Z}$ First note that when $p$ is prime and $1\leq r\leq p-1$ the binomial coefficient $$\binom{p}{r}=\frac{p!}{r!(p-r)!}$$ is ...
1
vote
2answers
50 views

Find the lowest degree of the polynom $P$?

I have to determine the lowest degree of $P$ given by the following system : $\left\{ \begin{array}{l} P \equiv 2X \ \mod[X^2 -2X +1] \\ P \equiv 3X \ \mod[X^2 -4X+4] \end{array} \right.$ First, ...
3
votes
1answer
39 views

Algebraic closure for rings

Is there any notion of algebraic closure for commutative rings? I am specifically interested in such a concept for $\mathbb Z_n$, with $n$ not a prime (possibly square-free). Such a concept would be ...
2
votes
2answers
37 views

Given that $1 = 27 \times 11 - 74 \times 4$, solve the following equations in modulo $74$: $ 3x - y = 1$; $2x + 3y = 0$

Given that $1 = 27 \times 11 - 74 \times 4$, solve the following equations in modulo $74$: $3x - y = 1$; $2x + 3y = 0$. Thank you.
-1
votes
0answers
13 views

If the euclidean algorithm is used to solve an equation ( i.e., $ax = b \mod(z)$) is the solution unique?

I have solved such an equation using the euclidean algorithm. However, unlike other methods, this gives one solution. Is this just one solution or the only solution. Help is much appreciated. Thank ...
-3
votes
1answer
29 views

Modular arithmetic equivalent [closed]

Let $A, B, C$ are integers from $1$ to $9$. In order to get an integer from this operation, A*B/C, I've devised two formulas. $(A*B) \pmod C$. $(A \pmod C)$ or $(B \pmod C)$. These two are not ...
2
votes
3answers
30 views

Simple mod 7 problem

I need to Show that $7x^3 + 2 = y^3$ has no solutions in integers x and y. The solution I am given is: Suppose there are solutions to this equation. Then mod 7 we have $2 ≡ y^3$ (mod $7$) and hence ...
1
vote
2answers
25 views

Sequence of perfect squares

Let $a,b\in \mathbb{N}$. Prove that, if $a$ is quadratic residue modulo $b$, then sequence $(a+kb)$, $k\in \mathbb{N}$, has infinite amount of perfect squares. How should I approach this ...
7
votes
2answers
111 views

Prove: if $n\mid 7^n+6^n$ and $n>1$, then $13\mid n$

Prove: if $n\mid 7^n+6^n$ and $n>1$, then $13\mid n$ Let $p$ be the least prime number such that $p\mid n$. And I want to show that $p=13$ Let $d$ be the least number such that: $14^d\equiv 0 ...
0
votes
3answers
46 views

Congruence $320 \equiv 1 (\text{mod }x)$ [closed]

I have the following congruence $320 \equiv 1 (\text{mod }x)$ And the question is : find all the modulos $x$ that make this congruence true.
1
vote
1answer
27 views

Standard definition for $a$ being congurent to $b$ mod $n$

My text puts the definition for $$a\equiv b \bmod n$$ as $$n\mid(a-b).$$ On the other hand, certain sources puts the definition as $$n\mid(b-a).$$ Which exactly is the standard notation or is there a ...
3
votes
2answers
198 views

How to calculate a Modulo?

I really can't get my head around this "modulo" thing. Can someone show me a general step-by-step procedure on how I would be able to find out the 5 modulo 10, or 10 modulo 5. Also, what does this ...
0
votes
0answers
15 views

Showing irreducibility of polynomials of degree 3 over the rationals

Let $\ g = X^3\ -9X + 16 $. Prove that $g$ is irreducible over the rational numbers. So far I have used reduction modulo $5$ and this gives $g_5 = X^3 +X + 1$. Then I get $$ g_5(0) \equiv 1 \pmod5,\\ ...
5
votes
3answers
51 views

$a^{13} \equiv a \bmod N$ - proof of maximum $N$

From Fermat's Little Theorem, we know that $a^{13} \equiv a \bmod 13$. Of course $a^{13} \equiv a \bmod p$ is also true for prime $p$ whenever $\phi(p) \mid 12$ - for example, $a^{13} = a^7\cdot a^6 ...
1
vote
2answers
31 views

Equality symbols in modular arithmetic

E.g., can I write $(a^{p})^{2p} \equiv a^{2p}=a^pa^p\equiv aa\equiv a^2\pmod{\! p}$? I often see equality symbols inbetween mod equivalences. The equality signs point out the equality is not ...
3
votes
0answers
16 views

System of linear congruence, not relatively prime

Consider we have the following set of congruences $$x\equiv b_i \pmod {m_i}$$ for all $1\leq i\leq d$. $m_i$'s doesn't have to be relatively prime, so the Chinese remainder theorem doesn't work here. ...
3
votes
2answers
70 views

what is remainder when $(((3!)^{5!})^{7!})^{9!…}$ is divided by 11

$$(((3!)^{5!})^{7!})^{9!...}$$ when divided by 11 what will be the reminder? Hint is appreciated Sorry I do not know how to start this problem, so I have not shown my efforts!
0
votes
0answers
20 views

Proof of an congruence modulo n [duplicate]

I've the following theorem: For $n\in\Bbb Z$, prove that $n^3\equiv n \pmod{6}$ Please check whether I produced a good proof: 1) Let $k,n\in\Bbb Z$ s.t. $6=kn$ since $n^{3}$ is congruent to $n ...
1
vote
2answers
20 views

Proof of a congruence relation

Let n∈N, and let a,b∈Z. Suppose that a≡b (mod n). Prove that n|a if and only if n|b. As can be proceed?
1
vote
2answers
19 views

Equivalence classes in $\mathbb{Z}_n$

I've the following exercise: Solve each of the following equations in the given set $\mathbb{Z}_n$: 1) $[5]+x=[1]$ in $\mathbb{Z}_9$ 2) $[2]\cdot x=[7]$ in $\mathbb{Z}_{11}$ For 1), is $x=5$ ...
0
votes
5answers
70 views

Prove that $n^3=n \text{ mod }6$ for every integer $n$. [duplicate]

Prove that for every integer $n$ , $n^3=n \text{ mod }6$ I was having no clue how to do this, then I thought of case-by-case analysis and obviously it worked. The problem is that there were six case ...
0
votes
2answers
24 views

Two real numbers which belong to distinct classes in the quotient group $\mathbb R/\mathbb Z$.

Let $x,y$ two real numbers. What does mean, in "pratical terms", that "$x,y$ belong to distinct classes in the quotient group $\mathbb R/\mathbb Z$"? Maybe that their difference $x-y$ isn't an integer ...
4
votes
3answers
54 views

On the distribution of multiples of 7 into intervals of length 11

Say we have two primes, say 7 and 11. We are to consider the positions of the multiples of 7 inside the (7 buckets of) multiples of $11$. So the buckets of 11 are: $[1,11],[12,22],\ldots ,[67,77]$, ...
1
vote
1answer
72 views

Solving to find the general equation with a “mod” equation

They probably aren't called "mod" equation but i couldn't think how else to word them, so I have this equation $8x + 10y ≡ 8 \pmod 7$ And have been tasked with finding the general solution, I know ...
2
votes
1answer
43 views

Sequence of real numbers which are distinct modulo 1.

Let $\{x_n\}_{n\in\mathbb N}$ a sequence of real numbers which are distinct modulo 1. Are the sequences $$\{\varepsilon x_n\}_{n\in\mathbb N} \ \ (\varepsilon\rightarrow 0), \ \ \ ...
2
votes
2answers
62 views

Number of fingers of a Martian

I have a question about what seems to be modular arithmetic, but I can't quite get the answer. The problem goes along the lines of: It is often said Earthlings use the decimal system because they ...
2
votes
1answer
61 views

What is $13^{498}$ (mod $997$)? [duplicate]

I have to determine $$13^{498} \pmod{997}$$ I know that it can only be $1$ or $-1$. But I don't quite know which. How can I decide?
1
vote
1answer
53 views

Modulus differentiation

For a Java project, I need to find a way to compute the derivate of a modulus function like $$f(x) = g(x) \pmod{h(x)}$$ for any value of $x$. I know that the modulus function is discontinuous. If ...
1
vote
1answer
51 views

Show the congruence $x^{p-1}\equiv 1\pmod{p}$ has $p-1$ solutions

Question: Let $p$ be prime. show the congruence $x^{p-1}\equiv 1\pmod{p}$ has $p-1$ solutions Attempt: I know by Lagrange's theorem that this congruence will have at most $p-1$ solutions since $p-1$ ...
0
votes
0answers
7 views

Modular arithmetic of rotation a triange

A triangle is an n-gon with 3 rotational symmetries and 3 reflection symmetries. Each rotation is 120 degrees. Suppose the triangle begins with initial angle 240 degrees and rotates through 240 ...
0
votes
1answer
43 views

How to solve congruence modulo equations?

While studying Affine Cipher in cryptography it tells that we need to solve a system of modulo congruence equations. The equations are: $8\alpha+\beta\equiv 15 \pmod{26}$ $5\alpha+\beta\equiv 16 ...
0
votes
1answer
32 views

Show that if $a, b$ and $m$ are integers such that $m \geq 2$ and $a \equiv b \pmod{m}$, then $\gcd(a, m) = \gcd(b, m)$

Problem 1 (#3.5.32). Show that if $a, b$, and $m$ are integers such that $m \geq 2$ and $a \equiv b \pmod {m}$, then $\gcd(a, m) = gcd(b, m)$. Proof. Let $d = \gcd(a, m)$ Then $d \mid a$ and $d ...
2
votes
1answer
36 views

Hensel's lemma modular arithmatic example problem

In an example for Hensel's Lemma we have met the criteria to use Hensel's lemma and have begun to apply it in a Hensel's iteration. We have $f(x)=x^2+1$ and our initial $x_0=2$ is a solution ...
1
vote
1answer
31 views

Number of possible solutions in modular equation

I have given the result value $z$. I know that $$z \equiv x\cdot(x-1)\pmod p$$ where $p$ is prime and the value $p$ is fixed and given. I have also given the information, that $x \in \{m, M\}$, where ...
0
votes
1answer
25 views

Digital Signatures using RSA

RSA can be used for digital signatures this way: B creates $m$ (product of two primes), $r$ (a number for what gcd($r$, $\Phi(m)$ equals 1) and tells $m$ and $r$ A. B chooses $s$ which is the ...
1
vote
1answer
38 views

modulo RSA decrypt question

Given the following RSA generated public key: $P(3, 55)$. Which integer value should be chosen for $d$ to decrypt messages encrypted with $P$? Check your answer with $M = 8$ and $C = 17$. ...
3
votes
4answers
44 views

Find the following integer $ x $, s.t. $x \equiv 7^{57} \pmod {133}$

Find the following integers $x$: $x \equiv 7^{57} \mod 133$ I need to use fermat's little theorem for this problem which I know. It is for a prime number p. Then $a^{p-1} \equiv 1 \pmod p$ but I do ...
2
votes
2answers
30 views

Finding big exponential value

How to find the following most efficiently $$ A^{x} \bmod M $$ where $A,x\le10^{10}$ and $M$ is a quite big prime number.
0
votes
0answers
27 views

Reverse proof of Fermats Little Theorem [duplicate]

Let $n \in \mathbb{N}$. For all $x \in \{1,2,...n-1\}$ it is: $x^{n-1} \equiv 1 \text{ mod } n$. Show that $n$ is prime. This seems to be proving Fermat's little theorem the other way round. Until ...
0
votes
3answers
66 views

Find $19^{92} \pmod {92}$

How can I find $19^{92}\pmod{92}$? I am completely stumped. I thought of calculating $19^{92} \pmod{23}$ and $19^{92} \pmod{4}$.. ( because $23\cdot4 = 92$). But I don't know the modulo operation ...