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
3answers
53 views

Calculate possible values of $a^4$ mod $120$.

Calculate possible values of $a^4$ mod $120$. I don't know how to solve this, what I did so far: $120=2^3\cdot3\cdot5$ $a^4 \equiv 0,1 \pmod {\!8}$ $a^4 \equiv 0,1 \pmod {\!3}$ $a^4 \equiv 0,1 ...
6
votes
1answer
54 views

Carmichael numbers of form $m^3+1$ and Ramanujan's $1729$

While researching for a post on tetranacci pseudoprimes I came across a list of Carmichael numbers, $$C_n = 561,\, 1105,\, 1729,\, 2465,\, 2821,\dots$$ Of course, Ramanujan's taxicab number $1729 = ...
2
votes
2answers
30 views

Question about working in modulo?

This question is in essence asking for understanding of a step in Fermats theorem done Group style. For any field the nonzero elements form a group under field multiplication. So let us take the ...
3
votes
4answers
86 views

What is $3^{43} \bmod {33}$?

I just took math final and one of the question was Find $3^{43}\bmod{33}$. So, I used Euler's function; $\phi(33)=20$. $3^{20}\equiv 1\pmod{\!33}$ By using this fact, I got $27$. One ...
0
votes
1answer
17 views

Prove that if $\{1^5,2^5,\ldots, (pq)^5\}$ is a complete residue system mod $pq$, then $\{1^5,2^5,\ldots,p^5\}$ is too, mod $p$

$p,q\ge 2$ are coprime positive integers. Prove that if $\{1^5,2^5,\ldots, (pq)^5\}$ is a complete residue system mod $pq$, then $\{1^5,2^5,\ldots,p^5\}$ is a complete residue system mod $p$. ...
4
votes
1answer
40 views

Sum of elements of a finite Field

Let $F$ be a finite field and $i$ an integer. Calculate the sum of all the elements of $F$,each raised to the $i-th$ power. My approach so ...
-3
votes
1answer
40 views

Show that $1^n+2^n+\cdots+(p-1)^n\equiv 0\pmod {\!p}$ [on hold]

Let $p$ be an odd prime, and let $n$ be an integer not divisible by $p-1$. Show that $$1^n+2^n+\cdots+(p-1)^n\equiv 0\pmod {\!p}$$
2
votes
1answer
30 views

Proving consecutive quadratic residue modulo p [duplicate]

Let p be a prime with p > 7. Prove that there are at least two consecutive quadratic residues modulo p. [Hint: Think about what integers will always be quadratic residues modulo p when p ≥ 7.]
-1
votes
0answers
22 views

Quadratic residue dependency on $\bmod 4$ [duplicate]

Let $p$ be an odd prime and let $a$ be a quadratic residue modulo $p$. Write a formal proof showing that $−a$ is also a quadratic residue modulo $p$ if and only if $p ≡ 1 \bmod 4$. I sort of ...
-1
votes
4answers
44 views

Last 2 digits of a product

What will be the last two digits of $25^{63} \cdot 63^{25}$? The answer is given as $25$ or $75$. What is the procedure to reach this answer?
1
vote
3answers
43 views

Why is Euler Theorem not working here?

$10^k \equiv 1 \pmod {\!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
6answers
33 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
2answers
48 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
votes
2answers
48 views

-a is also a quadratic residue mod p [on hold]

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.
4
votes
1answer
35 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?
2
votes
2answers
101 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
53 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 ...
3
votes
6answers
119 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
32 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
40 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
97 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
89 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
48 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
62 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
47 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
25 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
32 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
106 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
25 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
93 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
85 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
51 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
53 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
51 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
44 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
197 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
98 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
26 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 ...