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
2answers
47 views

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

Given that $1 = 27 \times 11 - 74 \times 4$, solve the following equations in modulo $74$: $3x - y = 1$; $2x + 3y = 0$. Thank you.
0
votes
1answer
31 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 ...
2
votes
3answers
109 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 ...
10
votes
2answers
249 views

$1989 \mid n^{n^{n^{n}}} - n^{n^{n}}$ for integer $n \ge 3$

Before anyone comments, yes this is kind of a duplicate of Prove that $1989\mid n^{n^{n^{n}}} - n^{n^{n}}$ . The problem that I'm having I don't see the $n=5$ as a counterexample. Also if anyone wants ...
1
vote
2answers
38 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
138 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
61 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
29 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 ...
4
votes
3answers
29k 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
39 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
68 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
78 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
71 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. ...
2
votes
3answers
112 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!
1
vote
2answers
25 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
22 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
94 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
27 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
84 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
117 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
53 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), \ \ \ ...
3
votes
4answers
187 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
119 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
184 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
69 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
1answer
215 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
52 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
74 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
94 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
37 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 ...
2
votes
1answer
75 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
62 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 ...
1
vote
2answers
41 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
3answers
97 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 ...
3
votes
2answers
137 views

Backwards proof of Fermat's Little Theorem

$$\textrm{Let }p \in \mathbb{N}. \textrm{ Show that }\forall n \in \left \{ 1,2,...,p-1 \right \} \textrm{if } n^{p-1} \equiv 1 \mod p \Rightarrow p \in \mathbb{P}$$ This is basically Fermat's ...
1
vote
1answer
82 views

how to solve system of quadratic equations (mod N)

Given a two equations: $${(ax_1 + b)}^2 = c_1 \pmod N$$ $${(ax_2 + b)}^2 = c_2 \pmod N$$ $N=p.q$ $p$ and $q$ are large primes $x_1, x_2$ and $c_1, c_2$ are known Is it computationally feasible to ...
1
vote
1answer
36 views

Consider the number $N=2015^{2015}$. What is the remainder of $N$ when it is divided by $4$? $11$? $44$?

The question: Consider the number $N=2015^{2015}$. What is the remainder of $N$ when it is divided by $4$? $11$? $44$? I used a modulo calculator to get that the answer for $N$ mod $4$ is $3$, and ...
11
votes
3answers
130 views

Show that for every prime $p$, there is an integer $n$ such that $2^{n}+3^{n}+6^{n}-1$ is divisible by $p$.

So the problem states: Show that for every prime $p$, there is an integer $n$ such that $2^{n}+3^{n}+6^{n}-1$ is divisible by $p$. I was thinking about trying to prove this using the corollary to ...
1
vote
1answer
50 views

Multiple roots in $\mathbb{Z}_p$

Let f(x) ∈ $\mathbb{Z}$[x], a polynomial of degree n. Suppose f(x) has n distinct roots $a_1, ..., a_n$ ∈ $\mathbb{C}$. Now, with a given f(x), we call a prime p "bad" if f(x) has a ...
1
vote
0answers
64 views

$5^x \equiv 1520 \pmod {9797}$ [duplicate]

How do you solve this? What does mod mean and how will I solve it? I understand that it can be solved but how? 5 to some exponent equals the (mod of 9797) what is the answer to this?
1
vote
9answers
96 views

Find integers $m$ and $n$ such that $14m+13n=7$.

The Problem: Find integers $m$ and $n$ such that $14m+13n=7$. Where I Am: I understand how to do this problem when the number on the RHS is $1$, and I understand how to get solutions for $m$ and ...
3
votes
3answers
107 views

Calculate possible values of $a^4$ mod $120$.

Calculate possible values of $a^4$ mod $120$. I don't know how to solve this, what I did so far: $120=2^3\cdot3\cdot5$ $a^4 \equiv 0,1 \pmod {\!8}$ $a^4 \equiv 0,1 \pmod {\!3}$ $a^4 \equiv 0,1 ...
7
votes
1answer
115 views

Carmichael numbers of form $m^3+1$ and Ramanujan's $1729$

While researching for a post on tetranacci pseudoprimes I came across a list of Carmichael numbers, $$C_n = 561,\, 1105,\, 1729,\, 2465,\, 2821,\dots$$ Of course, Ramanujan's taxicab number $1729 = ...
2
votes
2answers
43 views

Question about working in modulo?

This question is in essence asking for understanding of a step in Fermats theorem done Group style. For any field the nonzero elements form a group under field multiplication. So let us take the ...
5
votes
4answers
108 views

What is $3^{43} \bmod {33}$?

I just took math final and one of the question was Find $3^{43}\bmod{33}$. So, I used Euler's function; $\phi(33)=20$. $3^{20}\equiv 1\pmod{\!33}$ By using this fact, I got $27$. One ...
1
vote
1answer
151 views

If $\{1^5,2^5,\ldots, (nm)^5\}$ is a complete residue system mod $nm$, prove $\{1^5,2^5,\ldots,n^5\}$ is a complete residue system mod $n$.

Let $n,m\ge 2$ be coprime positive integers. Prove that if $\{1^5,2^5,\ldots, (nm)^5\}$ is a complete residue system mod $nm$, then $\{1^5,2^5,\ldots,n^5\}$ is a complete residue system mod $n$. ...
5
votes
1answer
307 views

Sum of elements of a finite field

Let $F$ be a finite field and $i$ an integer. Calculate the sum of all the elements of $F$, each raised to the $i$th power. My approach so ...
2
votes
1answer
155 views

Proving consecutive quadratic residue modulo p [duplicate]

Let p be a prime with p > 7. Prove that there are at least two consecutive quadratic residues modulo p. [Hint: Think about what integers will always be quadratic residues modulo p when p ≥ 7.]
1
vote
3answers
57 views

Why isn't Euler's theorem working to find the smallest $k$ such that $10^k \equiv 1 \pmod {\!9}$?

$10^k \equiv 1 \pmod {\!9}$ According to Euler's theorem and the Carmichael function, smallest $k$ is $\phi(9) = 6$, but clearly the smallest $k$ is $k=1$. What am I doing wrong?
0
votes
6answers
62 views

Finding the inverse of a number under a certain modulus

How does one get the inverse of 7 modulo 11? I know the answer is supposed to be 8, but have no idea how to reach or calculate that figure. Likewise, I have the same problem finding the inverse of 3 ...