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
2answers
17 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
34 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.
5
votes
2answers
114 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
153 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
2answers
60 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
118 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
13 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
31 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 ...
6
votes
3answers
198 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 ...
1
vote
2answers
42 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
87 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 ...
2
votes
0answers
99 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
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. ...
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
64 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 ...
-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 ...
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$, ...
-1
votes
1answer
31 views

Prove that $2n + m \equiv 0 \pmod3$if and only if $ n \equiv m \pmod3$ [closed]

Prove that $2n + m \equiv$ $0 \pmod3$ iff $n \equiv$ $m \pmod3$ Is there a way to prove this without proving both directions of the biconditional?
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
38 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 ...
-2
votes
0answers
53 views

Summation Direct Proof Help [closed]

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+1+2+3+4+5+6+7=24, and in fact, 11234567 ...
1
vote
1answer
28 views

Chinese remainder theorem to solve 3 mod 11 and 11 mod 13 [closed]

Im 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 3 mod 11 and 11 mod 13 and I've ...
-3
votes
3answers
75 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$?
9
votes
1answer
77 views

Solving a Diophantine equation: $p^n+144=m^2$

I found this Diophantine equation: $$p^n+144=m^2$$ where $m$ and $n$ are integers and $p$ is a prime number. I solved it but I want to know if there exist other proofs through the use of rules of ...
-2
votes
2answers
43 views

calculate reverse number with 2 conditions [on hold]

I can't find the reversed number of $2 \mod 13$ ($2^{-1}=?$) that is also a solution to $$5x = 2 \mod 13.$$ How can I find it? Thanks!
1
vote
1answer
437 views

Solving a non-linear congruence

How can we solve for $x$, knowing the integer $n$ and the real numbers $a$ and $b$, the following non-linear congruence: $(x+a)^2=-b\pmod{n}$ Specifically in this example: ...
2
votes
0answers
44 views

Are there Latin squares with no repeats on the diagonal not of the form 2y+x+1(mod n)?

I am looking for a certain kind of latin square (nxn). Rules: No repeats in any column or row (Definition of Latin Square) No repeats in any diagonal including others than the main diagonal. So ...
-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
2answers
31 views

Combining divisibility with congruences

If we assume that $x^2 - xy + y^2 \equiv 0 \pmod n$ Then $x^2 + y^2 \equiv xy \pmod n$ If $(x,y,n)=1$. Then we can observe that neither x nor y can divide the ...