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
4answers
43 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
12 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 ...
20
votes
4answers
2k views

Is the number $333{,}333{,}333{,}333{,}333{,}333{,}333{,}333{,}334$ a perfect square?

I know that if the number is a perfect square then it will be congruent to $0$ or $1$ (mod $4$). Now since the number is even, I know that it is either $0$ or $2$ (mod $4$). How would I go about ...
4
votes
1answer
31 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 , ...
6
votes
3answers
144 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 ...
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$ ...
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 ...
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 ...
1
vote
1answer
42 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 ...
4
votes
2answers
33 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 ...
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
1answer
31 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 ...
11
votes
1answer
169 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
4answers
31 views

Question on modulus

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

Fastest way to find modular multiplicative inverse

I am looking for a fast way to find the modular multiplicate inverse of an integer $a$ in mod $p$. I am mainly interested in ...
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?
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.
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...
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 ...
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
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 ...
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
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
1
vote
2answers
4k views

modular arithmetic, solving ax + b = c (mod d)?

For example 151x - 294 is congruent to 44 (mod 7). How would I go about solving that? The answer says to simplify it into the ax = b (mod c) form first, but I have no clue on how to get rid of the ...
2
votes
5answers
61 views

Possible solutions of a diophantine equation: $p^2+pq+275p+10q=2008$

What are couples of prime integers that verify this diophantine equation: $$p^2+pq+275p+10q=2008?$$ I tried to solve this equation trough the rules of modular-arithmetic. I rewrite the equation as: ...
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
2answers
55 views

Pythagorean Triple divisible by $5$

Show that, if x, y and z are integers such that $x^2+y^2 = z^2$,then at least one of $x,y,z$ is divisible by $5$. I was able to show that at least one of $x$ or $y$ is divisible by $2$. Can someone ...
1
vote
1answer
223 views

Why does this sum mod out to 0?

In making up another problem today I came across something odd. I've been thinking it over and I can't exactly place why it's true, but after running a long Python script to check, I haven't yet found ...
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 ...
2
votes
16answers
3k views

How to Prove the divisibility rule for $3$

The divisibility rule for $3$ is well-known: if you add up the digits of $n$ and the sum is divisible by $3$, then $n$ is divisible by three. This is quite helpful for determining if really large ...
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 ...
8
votes
1answer
190 views

Reduction modulo p of a linear group over the rational numbers

A paper (http://arxiv.org/pdf/1407.3158v2.pdf) contains the following theorem: Suppose $\mathbb{G}$ is a connected, simply connected, semisimple algebraic group defined over $\mathbb{Q}$, and let ...
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 ...
-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
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 ...
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$?