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
1answer
17 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
26 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
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 ...
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 ...
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?
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
2answers
135 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
168 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
207 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
89 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
44 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
37 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 ...
-1
votes
1answer
20 views

How to prove this modular propositions [closed]

Let $a$, $b$, $c$ be non zero terms in $\mathbb{Z}_p$ ($p$ is prime). $\operatorname{ord}(c)$ is the minimal natural number $r$ such as $c^r \equiv 1\pmod{p}$. 1) If $c^r \equiv 1 \pmod{p}$ and $c^q ...
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
40 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 ...
0
votes
0answers
42 views

Solving RSA cipher without calculator

I have a question: Encrypt the message UPLOAD using RSA with $n=3\cdot 31$ and $e =17$. My question is, how can I solve this with a calculator and in an efficient manner due to being in an exam ...
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: ...
0
votes
2answers
41 views

Factorization in modular arithmetic

Is this expansion a legal step? $12^8\mod15 = 2^8 * 2 ^ 8 * 3 ^ 8\mod15$
0
votes
0answers
44 views

Collatz algorithm generalization try-out (Collatz k-algorithm)

Recently I have been reading about the Collatz conjecture here in Mathematics Stack Exchange, and also found the fantastic paper of professor Lagarias about it. Everything was so interesting (and I ...
0
votes
0answers
20 views

Number of times the loop is executed

Initially I have provided x and y and the value of x and y repeatedly calculated until at some point the sequence is start repeating. ...