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
2answers
108 views

If $ p $ is an odd prime and $ D $ an integer not divisible by $ p $, show that $ x^2 - y^2 \equiv D ~ (\text{mod} ~ p) $ has $ (p - 1) $ solutions.

I am supposed to have proved the following congruence identity: $$ 1^{n} + 2^{n} + \cdots + (p - 1)^{n} \equiv 0 ~ (\text{mod} ~ p). $$ This is apparently meant to help me solve the problem stated in ...
-2
votes
5answers
59 views

Solving $7a + 8 \equiv 5 \pmod{11}$

Solve $7a + 8 \equiv 5 \pmod{11}$. I am having trouble answering this math problem. The final answer should work out to be $a = 9$ but I quite simply don't know to get that answer.
0
votes
1answer
31 views

Real numbers modulo $1$.

In teaching material of my professor I read "where $x_1,x_2,...,x_m$ are distinct real numbers modulo $1$". What is the definition of numbers modulo $1$? Intuitively I would say that there exist a ...
4
votes
6answers
145 views

(14^2014)^2014 mod 60 without a calculator

Calculate without a calculator: $\left (14^{2014} \right )^{2014} \mod 60$ I was trying to solve this with Euler's Theorem, but it turned out that the gcd of a and m wasn't 1. This was my ...
2
votes
2answers
38 views

Needing help finding the least nonnegative residue

$2^{47} \bmod 23$ $776^{79} \bmod 7$ $12347369^{3458} \bmod 19$ $5^{18} \bmod 13$ $23^{560} \bmod 561$ I really don't understand how to calculate the ones to powers. Could anyone explain how to ...
1
vote
3answers
45 views

Find the least nonnegative residue of $3^{1442}$ mod 700

So I have that $700=7\cdot2^2\cdot5^2$ and I got that $3^2\equiv1\pmod2$ so then $3^{1442}\equiv1\pmod2$ also $3^2\equiv1\pmod{2^2}$ so $3^{1442}\equiv1\pmod{2^2}$ which covers one of the divisors of ...
4
votes
0answers
57 views

Find all positive values for j,k,l such that j, k, l are positive integers and (j-k)|l, (k-l)|j, (l-j)|k.

Find all possible values of $j,k,l$ such that $j, k, l$ are positive integers and $(j-k)|l, (k-l)|j, (l-j)|k$. As I understand that using divisibility properties, it is possible to come to some ...
3
votes
5answers
101 views

How to find $2^{37} \bmod 77$?

Is there any quick way to find $2^{37} \bmod 77$? I have tried breaking it down into 2 components for example .. $2^{37} \bmod 7$ and $2^{37} \bmod 11$ but still no luck. Any ideas? Thanks
4
votes
2answers
119 views

Euler Fermat with double exponent [duplicate]

I have to calculate $$ 3^{{2014}^{2014}} \pmod {98} $$ (without calculus). I want to do this by using Euler/Fermat. What I already have is that the $\gcd(3, 98) = 1$ so I know that I can use the ...
0
votes
2answers
54 views

Find the least nonnegative residue of $68^{105} \pmod{13}$.

I did a problem before this, which was finding the least nonnegative residue of $2^{204} \pmod{13}$. Because $2^{6} ≡ 1 \pmod{13}$, I said that $(2^{6})^{34}≡1^{34} \pmod{13}$, and so I concluded that ...
3
votes
5answers
65 views

The residue of $9^{56}\pmod{100}$

How can I complete the following problem using modular arithmetic? Find the last two digits of $9^{56}$. I get to the point where I have $729^{18} \times 9^2 \pmod{100}$. What should I do from ...
2
votes
2answers
92 views

Numbers of the form $5 \cdot 2^{n}-1$ divisible by $3^k$ for large values of $k$

Let $n_k$ be the smallest integer such that $5 \cdot 2^{n_k}-1$ is divisble by $3^k$ where $k$ is a positive integer. Can one say something about the growth of $n_k$ with respect to $k$ ? Is it ...
2
votes
0answers
32 views

Is the multiplication modulo $p$ for polynomials well-defined?

Is the multiplication modulo $p$ for polynomials well-defined ? I mean let $g,h\in\mathbb Z[x]$ and let $\bar g$ be the polynomial obtained from $g$ by reducing all the coefficients of $g$ modulo ...
1
vote
1answer
52 views

How many solutions to $x^d\equiv a\pmod {p}$?

If $\gcd(d,p-1) = 1$, there is a unique solution to $x^d \equiv a \pmod p$. If $\gcd(d,p-1) > 1$, there are exactly $d$ solutions to $x^d\equiv a\pmod p$. $p$ prime, $d\ge 1$, ...
1
vote
1answer
36 views

Grid Problem Proof

I have a 2x2 grid square say, I can fit a shape like this: Such that there is one missing square. I can arrange this in any way so that the missing square can be located anywhere. I can do ...
6
votes
1answer
119 views

How to prove that $a=z^{p}$ for some $z \in \mathbb{Z_{+}}$?

Claim : If for a positive, composite integer $a$ and an odd prime $p$, such that $\gcd(a,p)=1$, we are given $$ a^{p^{n-2}(p-1)} \equiv 1 \pmod {p^n} \ \forall \ n \geq 2 \ \ ;\ ...
1
vote
1answer
28 views

If $p$ is an odd prime with $(p - 1)/2$ primitive roots, is $p$ a Fermat prime?

If $p$ is an odd prime and there are $(p - 1)/2$ primitive roots modulo $p$, then is $p = 2^k + 1$ for some nonnegative integer $k$? This is the converse of a statement that I have already ...
0
votes
2answers
27 views

Should the order of $a^k$ be $h/k$ as opposed to $h/(h,k)$?

Previously shown: Let $m\in\mathbb{N}$ and $a\in\mathbb{Z}$ s.t. $(a,m)=1$. Then the order $d$ of $a$ modulo $m$ exists and $d\mid\phi(m)$. Moreover, whenever $a^k\equiv 1\pmod{m}$, one has $d\mid ...
3
votes
4answers
95 views

$5x\equiv3\pmod3$

The answer from class is $x = 3 + 3t$ , $t$ belongs to $\mathbb Z$ I see that: 0 1 2 0 1 2 0 1 2 0 0 1 2 3 4 5 6 7 8 9 Am I understand this right? What is the proper way to find this answer?
5
votes
6answers
91 views

Why does the equation $x^2\equiv2 \pmod 5$ have no solutions?

Why does the equation $x^2\equiv2 \pmod 5$ have no solutions? I did a remainders table and found that $$x^2\equiv0;1;4\pmod 5$$ But is there any way to justify this besides that? The original ...
0
votes
2answers
28 views

Show if $(a,p)=1$ there is a unique inverse of $a$ modulo $p$

In a proof of Wilson's theorem, I read this identity and just wondered how to prove it: When $1\leq a\leq p-1$, we have $(a,p)=1$, so there exists a unique $\overline{a}$ with $a\overline{a}\equiv ...
3
votes
1answer
28 views

Diffie Hellman calculate number

I want to solve this Diffie Hellman problem: public number: $g=5$ prime number: $p=23$ Alice: Secret number $a < p$, $m\equiv g^a\mod p$ $m=21$ Bob: Secret number $b < p$, $n=g^b\mod p$ ...
0
votes
2answers
35 views

How do i prove that if $n$ is prime then $Z_n^*$ is a group under multiplication?

I want to prove that if $n$ is prime then $\mathbb{Z}_{n}$ is a field. I have been told that if $n$ is prime $\mathbb{Z}_{n}$ is a group under multiplication and thus $\mathbb{Z}_{n}$ is also a field. ...
0
votes
2answers
52 views

Group of units in the rings $\mathbb I_9 $ and $\mathbb I_{15}$?

The question I need help is: Prove that $U(\mathbb I_9) \cong \mathbb I_6$ and $U(\mathbb I_{15}) \cong \mathbb I_4 \times \mathbb I_2$. U() is the group of units in a ring All the "I" are ...
3
votes
2answers
50 views

Find all solutions to $2x \equiv p \mod 3p$

Find all solutions to $2x \equiv p \pmod {3p}$. $p$ is prime, and $p > 3$. I found that this is equal to $2x = p(3k+ 1)$ for some $k \in \Bbb{N}$. Since $k$ can't be even, then we have $2x = ...
2
votes
2answers
78 views

How can I prove the polynomial f is irreducible

We have $f\in \mathbb{Z}_{3}\left[X\right],\:\:f=x^3+2x^2+a,\:\:a\in \mathbb{Z}_{3}$ and we need to find $a$ for which polynomial $f$ is irreducible. I looked on google but I don't understand very ...
0
votes
2answers
54 views

Show that an even integer exists at the end

Start with positive integers: $1, 7, 11, 15, ..., 4n - 1$. In one move you may replace any two integers by their difference. Prove that an even integer will be left after $4n - 2$ steps. I said, ...
0
votes
1answer
33 views

Modulo arithmetic question

I'm reading Eulers criterion for quadratic residues, and have found his formula: if a number a is a quadratic residue than $a^{(p-1)/2} = 1$. But I am reading through the examples in Wikipedia, and ...
1
vote
1answer
63 views

Solving quadratic equations in modular arithmetic

Is there a general way to solve quadratic equations modulo n? I know how to use Legendre and Jacobi symbols to tell me if there's a solution, but I don't know how to get a solution without resorting ...
6
votes
8answers
206 views

Why is $n^2+4$ never divisible by $3$?

Can somebody please explain why $n^2+4$ is never divisible by $3$? I know there is an example with $n^2+1$, however a $4$ can be broken down to $3+1$, and factor out a three, which would be divisible ...
5
votes
3answers
112 views

How to quickly compute $2014 ^{2015} \pmod{11}$

Without using Fermat's Little Theorem, how can I quickly solve $2014 ^{2015} \pmod {11}$?
2
votes
1answer
77 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
29 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
53 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
25 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
40 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
73 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
25 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$ ...
4
votes
2answers
44 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
33 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
38 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
81 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
24 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?
7
votes
2answers
181 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
192 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
23 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
15 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 ...
3
votes
4answers
141 views

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

How to solve $x^3\equiv 10\pmod{990}$? It has 3 solutions: 10, 340, 670 (WolframAlpha).
2
votes
2answers
39 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
68 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...