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

1
vote
3answers
106 views

Inverse | Modulo | Power

Describe the inverse of $5$ modulo $18$ as a positive power of $5\pmod{18}$. I've got that the inverse of $5$ is $11$, but is this question asking to find a $t$ such that $$ 11=5^t\pmod{18}?$$
2
votes
1answer
58 views

REVISTED$^1$ - Order: Modular Arithmetic

Relevant Literature: Question: Observe that $2^{10}=1024≡−1 \pmod{25}$.Find the order of $2$ modulo $25$. Thoughts: Direct answers are OK, but I'd like to know if I'm right that what I'm really ...
4
votes
3answers
105 views

Evaluating $48^{322} \pmod{25}$

How do I find $48^{322} \pmod{25}$?
0
votes
1answer
53 views

Matrix inverses over finite fields with composite moduli

I know that over a field $F$, a matrix is invertible if and only if its determinant is nonzero. And I understand why this is true, at least in the case where the field is $\mathbb{R}$. But I do not ...
1
vote
1answer
73 views

RSA encryption theory - modulo theory

I'm a bit mathematically challenged and have been working on the RSA cipher (good start). I can find the public and private keys and know how to work do modulo operations on a calculator. The problem ...
0
votes
1answer
44 views

What value minimizes the error from a set of values under modular arithmetic?

I'm working with real numbers using modular arithmetic, say in the range [0,12). I would like to calculate some kind of 'modular mean' over a set of values $X$ that minimizes the total error. In other ...
1
vote
2answers
401 views

Find the modular residue of this product..

Please help me solve this and please tell me how to do it.. $12345234 \times 23123345 \pmod {31} = $? edit: please show me how to do it on a calculator not a computer thanks:)
2
votes
3answers
99 views

Show that no number of the form 8k + 3 or 8k + 7 can be written in the form $a^2 +5b^2$

I'm studying for a number theory exam, and have got stuck on this question. Show that no number of the form $8k + 3$ or $8k + 7$ can be written in the form $a^2 +5b^2$ I know that there is a ...
2
votes
1answer
376 views

Find the smallest possible integer that satisfies both modular equations

Find the smallest positive integer that satisfies both. x ≡ 4 (mod 9) and x ≡ 7 (mod 8) Explain how you calculated this answer. I am taking a math for teachers course in university, so I'm worried ...
0
votes
1answer
41 views

Solving Modular Equations With Identities

$4+2x≡7 \pmod 8$ Find all possible solutions and note any identities. Identify how you found the solutions. Explain what identities are.
1
vote
1answer
56 views

Help with modular arithmetic

If$r_1,r_2,r_3,r_4,\ldots,r_{ϕ(a)}$ are the distinct positive integers less than $a$ and coprime to $a$, is there some way to easily calculate, $$\prod_{k=1}^{\phi(a)}ord_{a}(r_k)$$
5
votes
2answers
570 views

Solving equations involving modulo operator

In computer programming languages we have an operator called % which expresses the remainder between two numbers. For example $123\%100 = 23$. I have an equation evolving this operator, namely, ...
2
votes
2answers
134 views

Chinese remainder theorem issue

Let's say I have the following equations: $$x \equiv 2 \mod 3$$ $$x \equiv 7 \mod 10$$ $$x \equiv 10 \mod 11$$ $$x \equiv 1 \mod 7$$ And I need to find the smallest x for which all these equations ...
1
vote
1answer
2k views

HINT for summing digits of a large power

I recently started working through the Project Euler challenges, but I've got stuck on #16 (http://projecteuler.net/problem=16) $2^{15} = 32768$ and the sum of its digits is $3 + 2 + 7 + 6 + 8 = ...
2
votes
1answer
82 views

Quadratic residues mod $n$ of $n-1$

While investigating something about square numbers, I started to wonder which numbers $n$ have quadratic residues of $n-1$. Obviously all $n$ of the form $m^2+1$ will work. But there are other numbers ...
5
votes
2answers
133 views

When is it solvable:$10^a+10^b\equiv -1 \pmod p$

If $p$ is a prime, $(a,p)=1$,denote $ord(a,p)=d,$ where $d$ is the smallest positive integer solution to the equation $a^d\equiv 1 \pmod p$.We can prove that $$10^n\equiv -1 \pmod p\tag1$$ is ...
2
votes
2answers
862 views

Doing modular division when denominator and modulus not coprime

So normally if you calculate $n/d \mod m$, you make sure $d$ and $m$ are coprime and then do $n[d]^{-1}\mod m$ , all $\mod m$. But what if $d$ and $m$ are not coprime? What do you do?
1
vote
1answer
300 views

Modulus Cancellation Law

I'm trying to understand the proof for cancellation law in modulus which states that: ...
3
votes
3answers
160 views

Finding inverse modulo

I'm trying to find "the smallest positive multiple of 100" that leaves remainder 9 when divided by 19. Here is what I have done before I got stuck: $x ≡ 9 \mod 19$ $\gcd(9,19) = \gcd(19,9)\\ ...
8
votes
4answers
1k views

Remainder when $20^{15} + 16^{18}$ is divided by 17

What is the reminder, when $20^{15} + 16^{18}$ is divided by 17. I'm asking the similar question because I have little confusions in MOD. If you use mod then please elaborate that for beginner. ...
1
vote
2answers
49 views

Remainders problem

What will be the reminder if $23^{23}+ 15^{23}$ is divided by $19$? Someone did this way: $15/19 = -4$ remainder and $23/19 = 4$ remainder So $(-4^{23}) + (4^{23}) =0$ but i didn't understand it ...
1
vote
1answer
75 views

Revised: Primes of form $p \equiv m \in S \mod x \ $

Refer to this question for background. I was speculating if there was an elegant way to define sequences A007645,A002313,A045357,A045407,A042986,A045331, A045425,A045374,A045400,A045350,A042988; ...
2
votes
2answers
117 views

Can you use modulus to make 0 > 2?

I wanted to create a rock-paper-scissors game that didn't use a lot of conditionals, and I was wondering if there were any mathematical way of representing the cycle of rock-paper-scissors. So Rock ...
0
votes
1answer
59 views

How to maximize $n!\sum^n_{k = 0}\frac{a^k(1+(-1)^{n-k})}{k!(n-k)!} \pmod{a^2}$ for a given $a$?

Short Version of the Question: How do I maximize the value of $n!\sum^n_{k = 0}\frac{a^k(1+(-1)^{n-k})}{k!(n-k)!} \pmod{a^2}$ for a given $a$? Long Version of the Question: I'm currently attempting ...
4
votes
3answers
833 views

The last 2 digits of $7^{7^{7^7}}$

What is the calculation way to find out the last $2$ digits of $7^{7^{7^7}}$? WolframAlpha shows $...43$.
1
vote
0answers
47 views

Synthetic Division with mods

$x^4+x+1$/ $2x^2$+1 In $F_5$ (means mod 5) I said let the leading coefficient be 2. Since $3$ $*$ $2$ - $5$ $*$ $1$ $=$ $1$, choose 3 to multiply $3$($2x^2$ $+$ $1$)= $x^2$ + $3$ (this is ...
4
votes
3answers
602 views

Congruences with prime power moduli

I'm trying to figure out the number of solutions to the congruence equation $x^d \equiv1 \pmod{p^2}$ where $p$ is prime and $d\mid p-1$. For the congruence equation ${x^d}\equiv1 \pmod p$ where $p$ ...
-2
votes
2answers
186 views

Use the modular exponentiation algorithm to find $13^{277} \pmod {645}$

I need to solve this question using the modular exponentiation method.
3
votes
2answers
64 views

Existence of a prime

If $x$ is odd and natural and ${x^2}+2\equiv3\mod 4$, how can I show there exists a prime $p$ such that $p|x^2+2$ and $p\equiv3\mod 4$.
2
votes
1answer
71 views

Modulo in e-voting paper is wrong?

I am trying to run in my mind the registration phase that exists in the paper: Internet Voting Protocol Based on Improved Implicit Security (pdf). I have chosen as parameters the following: the ...
1
vote
1answer
33 views

Computing $a^r \bmod n$ for a real number $r < 1$

I would like to calculate $d^{1/x} \bmod n$ where $d$ and $x$ belong to $\Bbb Z_n$. Here $x$ is greater than one, thus $1/x$ is less than one. How can I do a computation like that? For example what is ...
3
votes
1answer
104 views

$\mathbb{Z}/m\mathbb{Z}$: A Complete Set of Representatives

So, I'm letting ${\scr{A}}=\{a_1,\dots,a_n\}$ be a complete set of representatives (C.S.R.) for $\mathbb{Z}/m\mathbb{Z}$. I'm considering all $b\in \mathbb{Z}$ and seeing if ${\scr{B}}=\{a_1+b, a_2+b, ...
1
vote
4answers
69 views

$[4]_{17}[x]_{17} = [2]_{17}$: How to optimally solve this equality.

This notation is found in Concrete Introduction to Higher Algebra. Here is my method: For something like $[3]_{11}[x]_{11}^2=[4]_{11}$ I've just been using C++ code like this: ...
3
votes
1answer
98 views

How do you calculate $25^{11} \pmod{341}$?

How do you calculate $25^{11} \pmod{341}$? I understand you have to split the exponent into $11 = 1 + 2 + 8$?
0
votes
2answers
52 views

What does “Solve $ax \equiv b \pmod{337}$ for $x$” mean?

I have a general question about modular equations: Let's say I have this simple equation: $$ax\equiv b \pmod{337}$$ I need to solve the equation. What does "solve the equation" mean? There are an ...
2
votes
1answer
90 views

Related To Polynomial Division

How to prove the following result Show how a polynomial with odd number of term will never be divisible by a divisor with $x+1$ as factor for modulo $2$ arithmetic. I don't have any idea.
2
votes
1answer
51 views

Efficient modular exponentation of powers

Is there any way to efficiently compute $(((\mathrm{base}^{M_1})^{M_2})^{M_3} \dots )^{M_n}$ modulo $P$, where $P$ is prime? One way is to repeatedly do modular exponentiation for each of the powers. ...
0
votes
2answers
84 views

Is it true that $a^{k(p-1)+b} \;\stackrel{p}{\equiv} \;\;a^b\;$?

$$a^{k(p-1)+b} \;\stackrel{p}{\equiv} \;\;a^b\;?$$ $p$ prime number and $a,b,k\in\mathbb{N}^+$. And $p$ does not divide $a$. According to Fermat's Little theorem $a^{p-1}\stackrel{p}{\equiv}1$. So ...
2
votes
1answer
128 views

Congruence Classes in the Guassian Integers?

For some non-zero Gaussian integer n, how can I find a finite upper bound for the number of congruence classes mod n?
0
votes
1answer
165 views

Modulo expansion with divisor multiples

Is there any general expansion for 'a mod mn' ? mod is modulo operation: http://en.wikipedia.org/wiki/Modulo_operation ...
1
vote
1answer
76 views

Maximum order for $x$ in $g^x \equiv 1 \mod {n}$, when n=pq

I am currently trying to learn about the ElGamal Digital Signature scheme. It is based on the discrete logarithm problem, where it is computationally infeasible to find $x$ in $y=g^x \mod{p} $), if ...
2
votes
1answer
377 views

What software can calculate the order of $b \mod p$, where $p$ is a large prime?

I wasn't sure where to ask this, but Mathematics seems better than StackOverflow or Programmers. I have no background whatsoever in number theory, and I need to find software that can calculate the ...
1
vote
2answers
81 views

Show that for any uneven $n$ it follows that $n^2 \equiv 1 \mod 8$ and for uneven primes $p\neq 3$ we have $p^2 \equiv 1\mod 24$.

Show that for any uneven $n$ it follows that $n^2 \equiv 1 \mod 8$ and for uneven primes $p\neq 3$ we have $p^2 \equiv 1\mod 24$. My workings so far: I proceeded by induction. Obviously $1^2 \equiv 1 ...
2
votes
1answer
393 views

Computing $\bmod$s with large exponents by paper and pencil using Fermat's Little Theorem.

I'm having a bit of trouble computing $\bmod{mod}$s of large numbers using Fermat's Little Theorem. For example, how would you compute $7^{435627650}\mod 13$? The solution given is $435627650\mod ...
3
votes
4answers
84 views

Solving for Modular arithmetic

Solve the equation $38z\equiv 21 \pmod {71}$ for z. Little confused by the questions. My attempt is: $38 \odot z = 21.$ Then find the inverse of 38 from mod 71 and multiply both sides. Lastly, take ...
7
votes
2answers
191 views

Does there always exist an odd number of elements?

Given a nonzero integer $k$, does there always exist a positive integer $n$ such that there are exactly an odd number of elements $i\in\{0,1,...,n-1\}$ with $\frac{2^n-1}4 < 2^ik \mod{2^n-1} < ...
1
vote
1answer
85 views

Does $a \mid bc$ imply $\frac{a}{(a,b)} \mid c$?

If $a \mid bc$, then does $\frac{a}{(a,b)} \mid c$? I doubt anybody here is industrious enough to show this via a diagram, but who knows.
3
votes
1answer
62 views

Primitve roots and congruences?

Let $p$ be an odd prime. Show that the congruence $x^4$$\equiv -1\text{ (mod }p\text{)}\ $ has a solution if and only if $p$ is of the form $8k+1$. Here is what I did Suppose that $x^4$$\equiv ...
-1
votes
5answers
111 views

$(a,m) = (b,m) = 1 \overset{?}{\implies} (ab,m) = 1$

In words, is this saying that since $a$ shares no common prime factors with $m$ and $b$ shares no common prime factors with $m$ too, then of course the product of $a$ and $b$ wouldn't either!?
3
votes
6answers
144 views

$11$ divides $10a + b$ $\Leftrightarrow$ $11$ divides $a − b$

Problem So, I am to show that $11$ divides $10a + b$ $\Leftrightarrow$ $11$ divides $a − b$. Attempt This is a useful proposition given by the book: Proposition 12. $11$ divides a ...