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

0
votes
1answer
41 views

How can $n^5+4$ be a perfect square?

How can one find all $n \in \mathbb{N}$ such that $n^5+4$ is a perfect square? I see that $n^5=(x+2)(x-2)$ here im suck can someone help ?
2
votes
1answer
19 views

How to find cubic residues $\bmod p$ using WolframAlpha?

How to find cubic residues $\bmod p$ using WolframAlpha? Just type in "quadratic residues modulo p" and you're done, but typing in "cubic residues modulo p" does nothing. Logically, "x^3 ...
0
votes
4answers
45 views

$777^{401} \pmod {1000}$ is?

here's an arithmetic question : find the last $3$ digits of $777^{401}$. I don't know where to start. The chinese remainder theorem gives a double congruence modulo $8$ and $125$ but I don't think ...
0
votes
2answers
13 views

Proof that every quadratic residue has two roots, modulo a prime

Can someone provide a proof that every quadratic residue, when working in $\mathbb Z_p$, where $p$ is a prime, has exactly two roots? Indeed, there cannot be only one root as for any $a^2$, we know ...
4
votes
1answer
32 views

“congruence modulo 7” is an equivalence relation on Z. Find three elements in the equivalence class [3].

“congruence modulo $7$” is an equivalence relation on $\mathbb Z.$ Find three elements in the equivalence class $[3].$ so $3$ is congruent to $mod\ 7$.. My attempt: a = bq + r = 7(1) + 3 = 10 , ...
5
votes
2answers
53 views

How to decide which moduli to check when solving a “polynomial” congruence?

Consider the following problem: Find all integer solutions to $y^2 = x^5 - 4$. The solution goes something like – check modulo 11, where $x^5 \equiv 0, \pm 1$, and then check cases to arrive at ...
2
votes
1answer
18 views

Finding possible inverses of a modulo function

I know how to find $one$ inverse via the euclidean algorithm, but I can't figure out how to find more of them. For example: Find an inverse $x$, of $57$ $modulo$ $100$ Or an $x$ such that $57x ≡ 1$ ...
0
votes
1answer
27 views

Find $c$ in modular mathematics [on hold]

Suppose that $a$ and $b$ are integers, $a\equiv 11(\mod19)$ and $b\equiv3(\mod19)$ . Find the integer $c$ with following properties. $0\le c\le18$ $c\equiv 7a+3b(\mod19)$ $c\equiv2a^2 ...
4
votes
2answers
34 views

Eggs in a Basket (Remainders)

I'm working on a problem: A woman has a basket of eggs and she drops them all. All she knows is that when she puts them in groups of 2, 3, 4, 5, and 6, there is one left over. When she puts them into ...
0
votes
1answer
32 views

Find the residue of $(19^{33})(12^{17}) \mod 17$ using Fermat's Little Theorem?

Im somewhat familiar with the theorem and being able to reduce exponents to simpler forms and I also realize that I can break these two up into separate problems. But I cant quite connect the dots ...
0
votes
4answers
32 views

Question on modulus

Is $x|y$ the same as $x \equiv 0\! \mod\!{y}$ ? If not then how should it be written?
3
votes
2answers
56 views

Intuition behind quotient groups?

I am having a hard time seeing the intuition behind quotient groups or rings. Intuitively, for a group, say Z/nZ would the quotient groups be the different sub groups of order 0 to n-1? Or how would ...
0
votes
2answers
19 views

Can some of the case of this congruence be solvable? And what is the general way to solve this if it is solvable?

$a^m$ congruence to 1 (mod n) where a and n is not a coprime and m is an integer. How do you prove it if it is not solvable?
6
votes
3answers
145 views

What is the ten's digit of $7^{7^{7^{7^7}}}$

What is the ten's digit of $\zeta=7^{7^{7^{7^7}}}$. I got this question while doing binomial theorem. I think that $7^4=2401$ and we only need $\zeta\pmod{100}$. All I could think of is already ...
11
votes
1answer
172 views

A proof involving the Euler phi function

Problem: Let $\varphi$ be the Euler phi function, where for any $n \in \mathbb{Z^+}$, $\varphi(n)$ is the number of positive integers less than $n$ that are relatively prime with $n$. ...
0
votes
0answers
15 views

Modular arithmetic in Mod11 (Chilean RUT Check Digit)

First of all, I'm a lay, a sublunary mind in mathematical knowledge. I want to break this, but if I say something really stupid, please forgive me. In this article in Wikipedia, I found an algorithm ...
1
vote
0answers
14 views

Minimal column sum (?) solution to system of linear equations over $\mathbb{Z}_2$

There are $n$ equations in $n$ unknowns where both the coefficients and unknowns come from the field $\mathbb{Z}_2$. I can represent these as the equation $Ax = b$ where $A$ is an $n\times n$ matrix ...
4
votes
4answers
121 views

How to solve $x^3\equiv 10 \pmod{990}$? [on hold]

How to solve $x^3\equiv 10\pmod{990}$? It has 3 solutions: 10, 340, 670. Here is the link: https://www.wolframalpha.com/input/?i=x%5E3+%3D+10+%28mod+990%29
2
votes
2answers
32 views

Do inequations exist with congruences?

Gauss introduced the $\equiv$ symbol because congruences modulo $n$ were very similar to equality. But, by curiosity I would like to know if it was possible to write inequations such as: $$3x + 2y ...
0
votes
2answers
61 views

Find all solutions of equation $x^{23}=5$ in $\Bbb Z_{23}$

I just found that $5$ is a solution by using Fermat's theorem. But, I am not sure whether there are more solutions and how I could find them...
1
vote
3answers
30 views

Basic question about modular arithmetic applied to the divisor sum function $\sigma(n)$ when $n=5p$

While studying the divisor sum function $\sigma(n)$ (as the sum of the divisors of a number) I observed that the following expression seems to be true always (1): $\forall\ n=5p, p\in\Bbb P,\ p\gt ...
6
votes
3answers
208 views

I finally understand simple congruences. Now how to solve a quadratic congruence?

Now that I have plain old congruences, $19x\equiv 4 \pmod {141}$ for example, I am trying to wrap my brain around quadratic ones. My textbook shows how to tackle the aforementioned congruences, but ...
2
votes
5answers
90 views

Why $0$ in number $50$ is not a significant digit?

I have been reading definitions of significant figures which vary from source to source. 1-The digits in a number that indicate the accuracy of the number are called significant figures or ...
0
votes
2answers
35 views

Simplifying a decimal number under modular arithmetic – $9.9 \pmod{13}$

Can you please help me simplify the relation $9.9 \pmod{13}$? It may seem like a stupid question (!) but your answers will help me very much. Thank you.
1
vote
1answer
25 views

Show that if $x\equiv 1 \pmod {m^k}, $then $x^m \equiv 1\pmod{m^{k+1}}$.

Let $k\ge 1, m\ge 1.$ Show that if $x\equiv 1 \pmod {m^k}, $then $x^m \equiv 1\pmod{m^{k+1}}$. First I noticed that the assumption would imply $x^m \equiv 1 \pmod{m^k}$, but that doesn't seem to ...
1
vote
2answers
45 views

Arithmatic on modular curves

I had tried to read the first few pages of Glenn Stevens's$\,$ Arithmetic on Modular Curves, but it is somehow extremely unreadable to me, the text format is odd and stating too much facts without ...
0
votes
3answers
38 views

Modulo arithmetic proof

Show that if none of the numbers in the list 1a,2a,..(p-1)a are congruent to 0 mod p, then no two numbers in the list are congruent to each other mod p. I am not sure how to try to demonstrate this. ...
18
votes
3answers
4k views

Why does (1/3) mod 3016 = 2011?

So I am taking a class where we are working on a cryptography section. Basically, the course says that: $$\frac 1 3 \mod(3016) = 2011$$ or when run through Python - modified with SciPi: $$\frac 1 3 ...
1
vote
1answer
21 views

Is the set $V$ = { $([t], [g], [t], [j]): t,g,j∈$Z$,[2t+j] = [0]$} a subspace of vector space $(\mathbb Z_3)^4$?

Is the set $V$ = { $([t], [g], [t], [j]): t,g,j∈Z,[2t+j] = [0]$} a subspace of vector space $(\mathbb Z_3)^4$? I am inclined to think that it is a subspace. However, I cannot find any basis for the ...
0
votes
0answers
12 views

Way to evaluate sum of two set of modular square root.

I am wondering if there is a general way to calculate the following. Let $a, b, c, n$ be the integers and $p$ is the prime then, I am trying to evaluate $\left(\frac{a + \sqrt{b}}{c}\right)^n + ...
0
votes
1answer
25 views

Computing Large Number Modulo and Multiplicative Inverse

Prove that $3^{28}$ is a multiplicative inverse of $9^{34}$ modulo $17$, i.e. show that $3^{28}9^{34}\equiv 1\pmod {17}$. I really have no idea how to approach this example other than applying ...
1
vote
2answers
65 views

Analog clock with same hands - sometimes one can't tell time [duplicate]

There is an accurate analog clock, however both hands are the same size and shape. How many moments during a day a person can not conclude current time from the position of the hands? This is from a ...
0
votes
1answer
25 views

Quick question about mod equation

So here is the mod function: $$5 ^ {31} \cdot 2 ^{789} - 23^{23}\pmod{10}$$ Is there a way to shorten it, or I must calculate it plain numbers? I have tried the mod powers rule, but except for the ...
3
votes
3answers
47 views

Proving $93x + 47 \equiv 61 \pmod {101}$

I am preparing for an exam. I am dealing with this right now: $$93x + 47 \equiv 61\pmod{101}$$ However, I can't figure it out. Can someone describe steps for this example, or provide a link to any ...
0
votes
3answers
18 views

system of conguences

I am trying to figure out how to solve: Find $x, y \in \mathbb{Z}$ such that $$2x+y\equiv 4\pmod{17}$$ and $$5x-5y\equiv 9\pmod{17}.$$ I know this means $2x+y-4$ and $5x-5y-9$ are multiples of $17$, ...
2
votes
1answer
37 views

Proving $k$ is divisible by $3$ iff the sum of the digits of $k$ is divisible by 3 [duplicate]

I am trying to prove that $k$ is divisible by $3$ iff the sum of the digits of $k$ is divisible by 3 for all $k \in Z$. I am not even sure what tags to use because I am not sure of right methods to ...
1
vote
2answers
43 views

Summation Proof Dealing With 3s Multiples [duplicate]

So the problem is as follows: Prove that if the sum of digits of a decimal $n$ is three's multiple, then n is three's multiple by direct proof. For example, $11234567$ is 3's multiple because ...
1
vote
2answers
39 views

Proving $10^n \equiv 1 \pmod 3$ for all $n\geq 1$ by induction

Prove that $10^n \equiv 1 \pmod 3$ for all positive integers $n$ by mathematical induction. Can someone please help me in solving this problem and explain what's going on? Any guidance would be ...
1
vote
1answer
43 views

Chinese remainder theorem to solve $3 \bmod 11$ and $11 \bmod 13$

I'm trying to Decrypt a cipher text which has been encrypted using RSA and whose resulting value is $20$. Public parameters are $N = 143$ and $e = 17$. I've gotten down to equations $$x\equiv3 ...
-3
votes
3answers
78 views

How to show $20^3 \mod 11 = 3 \mod 11$? [closed]

How do I show: $$20^3 \mod 11 \equiv 3 \mod 11$$ I am very confused about this; please give a step by step way to solve this easily. Please don't use too much math jargon. Thanks
0
votes
0answers
29 views

Given $f=x^4+x+1 \in \mathbb Z_{2}[x]$ is primitive, write down an $m$-sequence ${a_n}$ associated to $f$

I'm not sure how to solve this question exactly. I know that the period will be 15 but I don't know how to construct the $m$-sequence.
1
vote
2answers
34 views

Existence of square root in $\mathbb Z_n$?

I had this question on my final exam and I struggled with it. It asks to prove or disprove the following: $$\forall m \in Z, \ \forall \ [a] \in Z_{m}, \ \exists \ [b] \in Z_{m}, [a]=[b]^{2} $$ ...
0
votes
1answer
29 views

The multiplicative group of integers modulo n

I need to write an introduction about the history who first showed that the multiplicative group of integers modulo $n$ is cyclic for certain $n$, when they showed it, why it was surprising, etc. ...
-1
votes
0answers
13 views

Modular Operations

Note: I am unsure how to properly format modular operations, so every operation here should be considered in its modular form. How do I do: $4*x-8=11$ in modulus set $11$?
1
vote
1answer
66 views

Find the multiplicative inverse of $5$ in $\mathbb Z_{73}$

I'm having some trouble with this question. The inverse should result in $44$ but I am getting $29$ $$73 = 14 \times 5 + 3$$ $$5 = 1 \times 3 + 2$$ $$3 = 1 \times 2 + 1$$ so $\gcd(73,5)=1$ using ...
-2
votes
1answer
19 views

Subgroups of $ \mathbb{Z}_n$ (integers mod $n$) [closed]

Is $\langle 15 \rangle$ a subgroup of $ \mathbb{Z}_{18}$ (the integers mod $18$)? There is a theorem in my book that says for every divisor $k$ of $n$, $\langle n/k \rangle$ is a subgroup of $ ...
2
votes
1answer
34 views

How to determine number of roots of $a^k + b^k \equiv c^k \pmod{d}$?

Is there a way to determine number of roots of $a^k + b^k \equiv c^k \pmod d$? It is an algorithmic task, not theoretic math. I am not looking for a closed formula.
0
votes
1answer
41 views

Number of solutions of the congruence $x^p \equiv x\pmod p$

How do I show that $x^p \equiv x\pmod p$ has precisely $p$ solutions? I can use Lagrange's theorem and Fermat's little theorem.
2
votes
2answers
42 views

Use Euclid's algorithm to find the multiplicative inverse $11$ modulo $59$

I was wondering if this answer would be correct the multiplicative of $11$ modulo $59$ would be $5$ hence $5\cdot11 \equiv 4 \pmod{59}$. Is this correct?
0
votes
0answers
19 views

Modulus Syntax in congruences

So I have some homework that has a notation I've never seen before and I can't find any documentation myself. Our professor gave us problems like this ...