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
29 views

Why is Euler Theorem not working here?

$10^k \equiv 1 \bmod 9$ According to Euler Theorem and Carmichael function, smallest $k$ is $\phi(9) = 6$, but clearly the smallest $k$ is $k=1$. What am I doing wrong?
0
votes
4answers
21 views

Inverse of a number within certain modular base

How does one get the inverse of (7) within mod 11 i know the answer is to be 8, but have no idea how to reach or calculate that figure likewise same here again, inverse of (3) within mod 13 is (9) ...
-1
votes
1answer
33 views

$x^2 \equiv a$ mod p, $x^2 \equiv b$ mod p, and $x^2 \equiv ab$ mod p, prove either all three are solvable or exactly one

Let p be an odd prime and a, b ∈ Z with p doesn't divide a and a doesn't divide b. Prove that among the congruence's $x^2 \equiv a$ mod p, $x^2 \equiv b$ mod p, and $x^2 \equiv ab$ mod p, either all ...
1
vote
1answer
16 views

-a is also a quadratic residue mod p

Let p be an odd prime and let a be a quadratic residue modulo p. Prove that −a is also a quadratic residue modulo p if and only if p ≡ 1 mod 4.
3
votes
2answers
28 views

Way to calculate exponent in congruent equation

I want to solve $$ 5^{x} \equiv 21 \pmod {23} $$ Is there a way to get the $x$ without trial & error?
0
votes
2answers
35 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 ...
0
votes
5answers
42 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
22 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 ...
2
votes
5answers
87 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
30 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
39 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
55 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
94 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
3
votes
2answers
81 views

Euler Fermat with double exponent

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
44 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 ...
-1
votes
0answers
25 views

How many elements in $\mathbb{Z}_{35}$ have cube roots?

How many elements in $\mathbb{Z}_{35}$ have cube roots? I am not sure how to answer this question. Do I need to use the Chinese remainder theorem in some way?
3
votes
5answers
60 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
1answer
43 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
23 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 ...
2
votes
1answer
47 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
30 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
101 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
23 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
24 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
90 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
84 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
25 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
32 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
50 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 ...
1
vote
3answers
17 views

How do I prove that $Z_n$ is a field if and only if n is a prime number greater than 1?

$Z_n$ is a field if and only if n is a prime number greater than 1. Is there a proof to show that this condition is necessary?
3
votes
2answers
48 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
50 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
50 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
39 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
196 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
97 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
64 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
23 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
1answer
21 views

Roots of the quadratics $x^2+5x+4$ and $x^2+8x-3$ modulo $45$ [closed]

how many roots of the two polynomials $x^2+5x+4$ and $x^2+8x-3$ in $Z_{45}$ have. Is there an easier way to do this ?
0
votes
4answers
51 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
20 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
35 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
69 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
19 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
28 views

Find $c$ in modular mathematics [closed]

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
36 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
32 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
36 views

Question on modulus

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