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

When is a number square in Galois field p^n if it's not square mod p?

Here is the problem, that I'm stuck on. There is no square root of $a$ in $\mathbb{Z}_p$. Is there square root of $a$ in $GF(p^n)$? Well, it's certainly true that $$x^{p^n}=x$$ and $$x^{p^n-1}=1$$ ...
0
votes
0answers
33 views

Calculate the product of $p(x)q(x) \pmod{x^3 +1}$

I need to calculate the product of $(x^2 + 3x + 1)(x^2 + 4x + 3)\pmod{x^3 + 1}$, where the product is in $\mathbb{Z}_5[x]$. Is this problem as simple as just multiplying the two, which would be $4x^4 ...
1
vote
2answers
37 views

How to prove $x^{\phi(m)+1}\equiv x\pmod{p}$ [duplicate]

How do I prove that $x^{\phi(m)+1}\equiv x\pmod{p}$ when $m=pq$, two distinct primes? I kind of have an idea that it involves Euler's Theorem but it doesn't seem to be working as well as I wanted it ...
1
vote
2answers
45 views

Find the least positive integer $x$ that satisfies the congruence $90x\equiv 41\pmod {73}$

Find the least positive integer $x$ that satisfies the congruence $90x\equiv 41\pmod{73}$. It is clear that an attempt to write this out as $90x-41=73n,\exists n\in \mathbb{Z}$ won't be very ...
0
votes
2answers
29 views

Repeated squaring method

How do I use the repeated squaring method to calcualte 2^176 (mod 177)? I'm not sure, but is there something about the fact that 177 is 1 greater than 176 that makes this a problem?
0
votes
2answers
45 views

Find the remainder if $19^{55}$ is divided by 13.

The question, as stated in the title, is Find the remainder if $19^{55}$ is divided by 13. Here is my approach for solving this problem. I know that $19\equiv6$ (mod 13), so $19^{55}\equiv ...
0
votes
1answer
41 views

Find conditions on $m$ and $n$ that ensure that $f$ is a bijection.

Given: $X=\{0,1,2,...,m-1\}$, $f:X\to X$, $f(x)=nx \pmod m$. Find conditions on $m$ and $n$ that ensure that $f$ is a bijection. Progress It seems that $(m,n)=1$ but I can't prove that. I tried ...
2
votes
1answer
53 views

Prove Euler's Theorem when the integers are not relatively prime

How can I prove Euler's Theorem: $$x^{\phi(m)+1} \equiv x \pmod m$$ is still true when $x$ is not relatively prime to $m$? Edit: when m=pq where p and q are distinct primes
4
votes
2answers
237 views

How can I test if an element g is a generator of a group G with a known number of elements, N?

Let's say $G$ has $1000$ elements. Without looping through each $g^m$, how can I show that $g$ is a generator? I've deduced that I must prove that the order of $g = N$, or in this case $1000$, but I'm ...
0
votes
1answer
27 views

Primitive roots of $2^{16} + 1$ [duplicate]

I have a primitive root $ \alpha $ of a number $ p = 2^{16} + 1$. How can I show if $ \alpha^{3} $ and $\alpha^{14}$ are primitive roots as well?
3
votes
2answers
250 views

Is this a legitimate proof? If not, how to prove?

Question: Determine all natural numbers $n$ such that: $7 \mid \left(3^n - 2\right) \implies3^{n}\equiv 2\pmod{7}$ Multiply both sides by 7 $7 \cdot 3^{n}\equiv 7\cdot2\pmod{7}$ Divide both sides ...
4
votes
4answers
87 views

Determining the last two digits of $229^{10} +37^{10}$

Determine the last two digits of: $229^{10}+37^{10}.$ I do not want to use the Euler-totient function or the carmichael function please! Thanks
1
vote
1answer
60 views

Given a, b How many solutions exists for x, such that: $a \bmod{x}=b $

Given $a, b$. How many solutions exists for $x$, such that: $$a \bmod{x}=b $$ By example: $a = 21$ and $b = 5$ $21 \bmod{8} = 21 \bmod{16} = 5$ Then $x$ has 2 solutions
0
votes
1answer
27 views

how many solution can be found of the form $A \pmod{X} = B$ [duplicate]

$A$ and $B$ are given, How many $X$ can be found to make the following equation true? $$ A \pmod{X} = B $$ Is there any formula?
0
votes
1answer
34 views

Prove homomorphism and surjectivity of a function

I have a question about this exercise for my math study: Let $d, n \in\mathbb{Z}_{>0}$ with $d\mid n$. a) Prove that there is a homomorphism $g: (\mathbb{Z}/n\mathbb{Z})^*\rightarrow ...
1
vote
2answers
40 views

How does this proof that the square of an integer, not divisible by 5, leaves a remainder of 1 or 4 when divided by 5 work?

Below I have a part of a proof of the fact that the square of an integer, not divisible by $5$, leaves a remainder of $1$ or $4$ when divided by $5$. But I am wondering where does the part highlighted ...
0
votes
1answer
38 views

homomorphism and resideu classes

I have a question about how I have to do this exercise for my math study: Let d, n $\in$ $\mathbb{Z}$>0 with d|n. a) Prove that there is a homomorphism f: $\mathbb{Z}$/n$\mathbb{Z}$ $\rightarrow$ ...
0
votes
1answer
16 views

Negative Modulo confusion

$$ x \equiv -74 \ mod \ 31 $$ According to Google & Wolframalpha the answer is 19 Following the method in this answer and using this answer I get 12. Using my calculator with this answer yeilds ...
0
votes
1answer
24 views

Find inverse modulo when modulo is smaller than the number

I know how to use the Euclidean algorithm to find the inverse modulo in most cases, but I can't wrap my head around the calculations when the modulo is smaller than the number I'd like to find the ...
0
votes
0answers
24 views

Minimization problem involving a set of prime numbers and modular arithmetics

I'm a student working for curiosity on a general minimization problem where I suppose that there is no efficient algorithm for solving it. I'd like to ask for your valuable advice. Let $P$ be a set ...
1
vote
3answers
45 views

$\pmod{n}$, proving that they are no integer solutions

Prove $5a^2\equiv k \pmod{12}$, where $k\in \{0,5,8,9\}$. Hence show that the equation $24x^7 + 5y^2 = 15$ has no integer solutions. My lecturer used a table containing $a$, $a^2$, and $5a^2$ from ...
6
votes
1answer
120 views

Find the last digit of the exponent $x$.

Let \begin{align} p&=396543857870745963499374527519378569849832249490600276007703072957912\cdots\\ &\phantom{=}8049490077183813353745228056691 \end{align} This number is a 100-digit prime ...
0
votes
2answers
48 views

How to get last digit of $7^{7^7}$

I want to find the last digit of $7^{7^7}$. I found out already that $7^7$ (mod 10) last digit is 3. But how do I use that to get the last digit of the whole thing? Thanks
1
vote
1answer
29 views

Fermat's Little Theorem - Prim. Root - Find x

So I am studying for finals and I am not able to solve the problem: Let $p=3∗2^{11484018}−1$ be a prime with 3457035 digits. Find a positive integer $x$ so that $2^x \equiv 3 \mod p$ Any guidance ...
3
votes
1answer
29 views

Find an integer $x$ such that $2^x \equiv 3\pmod{p}$ given prime $p$

So I am studying for finals and I am not able to solve the problem: Let $p=3\times2^{11484018}−1$ be a prime with 3457035 digits. Find a positive integer $x$ so that $$2^x \equiv 3 \pmod p$$ Any ...
2
votes
2answers
27 views

How to solve this congruence?

Given that $6^{12} ≡ 16\pmod {109}$. Is there a $k$ such that $16^k ≡ 6 \pmod {109}$? If there is, then find all the $k$'s. Does anyone know how to do this? Thanks
1
vote
1answer
10 views

Equivalence Relation Properties

I have to define whether the following relation is symmetric, reflexive, and transitive. Define a relation R on Z as follows: (x, y) ∈ R if and only if x = |y|: This is my answer so far: Is ...
1
vote
1answer
51 views

Find the residue of $1!+2!+…+n! \pmod{m}$ for $m>n$

Find the residue of $ 1!+2!+........+n! \pmod{m}$ for $m>n$ $n,m$ are positive numbers and need not be primes. is there any known proof or result for this thanks
0
votes
0answers
29 views

Could this discrete logarithm problem be proved?

Given some values $X$, $Y$, $A$, $B$ and $p$, is there a way to show that there exists (or doesn't exist) an $n$ such that $X = A^n \mod{p}$ and $Y = B^n \mod{p}$? Alternatively, are there particular ...
0
votes
3answers
19 views

Congruences - proof problems

1) State what is meant by $a\equiv b \pmod n$. 2) Suppose that $a\equiv b \pmod n$ and $c\equiv d \pmod n$. Prove that i) $a+c\equiv b+d \pmod n$ ii) $ac\equiv bd \pmod n$ For question 1, ...
0
votes
1answer
17 views

System of congruences with not coprime numbers

I have a system of congruences, for example $ x \equiv 2 \mod 15$ $ x \equiv a \mod 21$ where $a$ is an integer to be determined. I have to find all the values of $a$ for which the system has ...
2
votes
1answer
31 views

Modulo a composite number same as modulo individual factors?

Can somebody please give me a hint why the following holds (or doesn't it?): if $r^2 \equiv a \mod n$ and $n = p * q$, then $r^2 \equiv a \mod p$ and $r^2 \equiv a \mod q$. I tried it with ...
0
votes
2answers
39 views

Properties of addition and multiplication modulo $m$

I was studying some number theory and I came across this theorem in a book, but unfortunately there was no proof of it. Can somebody tell me the proof? $$(a + b) \bmod m = ( (a \bmod m) + (b \bmod m) ...
0
votes
3answers
36 views

Solve for the unknown

$31x-21^{21} \equiv 21+31^{31} \pmod 5$ The provided answers are: $$ \left\{ 3,8,13,18,... \right. $$ but I don't know how to get there. Can someone walk me through this please?
-1
votes
2answers
54 views

Prove this using modular arithmetic [closed]

$For n \in N$ Prove that: $\prod\limits_{x\in Z^*_n} x= \pm 1$ Thanks in advance!
0
votes
0answers
17 views

Prove this relation

Solve this: $y^2+2=x^3$ or Prove that $y^2+2=x^3 => (x,y)=(3,\pm 5)$ I know that it could be obvious to some of you by trial and error but I need a methodical approach. Thanks in advance!
0
votes
0answers
20 views

congruence, please hepl me solve this

$$ x^4 + x + 3 = 0 \pmod{3^3} $$ I'm not sure how to this, I've tried many times but it never works for me :/ so, I hope someone will help me
1
vote
0answers
21 views

Euler's criterion and Legendre symbol

I am working on an exercise which is the following : Let be $n$ an odd integer and $b$ such as $b \wedge n = 1$, then $(\frac{b}{n}) \equiv b^{(n-1)/2} \mod n$. (*) If $n$ is divisible by the ...
0
votes
0answers
18 views

Applying modulus to determinant

I'm have trouble understanding how to get the determinant of a matrix and apply a modulus to it. I have have $((6)(16) - (15)(5))^{-1} \mod29$ I have no idea how to break this down.
2
votes
0answers
28 views

Which primes satisfy this modular property?

Let $x$ be a residue$\mod p$ where $p$ is an odd prime. Im searching for such $p$ such that there exists a function $f(x)$ with propery $f(f(x)) - 2^x \equiv 0 \mod p $ for all values of $x$. I ...
2
votes
0answers
20 views

How to simplify expression with Fermat's little theorem

I don't quite understand how to reduce (25^74 + 53^27)^(10) I thought I would reduce to (4^74 + 4^27)^10 and then (4^(7*10 + 4) + 4^ (7*3 + 6))^(7*1 + 3) And then (4^4 + 4^6)^3 but that doesn't ...
1
vote
1answer
27 views

Polynomial greatest common divisor algorithem

I look for an algorithm for Polynomial greatest common divisor. I saw this at Wikipedia but I didn't understand where is the algorithm. If you have other source for this algorithm, or you can write ...
1
vote
4answers
33 views

Find the least significant digit

Explain why the number $(3^{27}\cdot7^{313}\cdot11^{121})^{1000}$ has 1 as its least significant digit. I know I am supposed to use $\pmod{10}$ but I am not sure how to combine the answers of the ...
0
votes
0answers
34 views

Reasoning behind the approach of finding modular multiplicative inverse

We know that if we want to find out the value of $\frac ab\pmod m $ we have to find out the modular inverse of b. If the modular inverse of b is x ,then we multiply x with a. Now ...
3
votes
4answers
49 views

Solving $3x\equiv 4\pmod 7$

I'm trying to learn about linear congruences of the form ax = b(mod m). In my book, it's written that if $\gcd(a, m) = 1$ then there must exist an integer $a'$ which is an inverse of $a \pmod{m}$. I'm ...
1
vote
3answers
12 views

How one can deduce that $tx≡2t[mod(z)]$?

Let $x,y,z,t$ four positive integers. If $$x≡2[mod(y)]$$ and $$z=ty$$ Then how one can deduce that $$tx≡2t[mod(z)]$$
11
votes
1answer
199 views

Solving $n^5+n^4-3=x^2\pmod p$

Prove that for every odd prime number $p$ there is a natural number $n$ such that the equation $n^5+n^4-3=x^2\pmod p$ has no solutions. So we have to understand that for each $p$ we can find $n$ ...
-1
votes
0answers
20 views

Prove divisibility - modular arithmetic

Could anyone help me solve this $For p\in prime, p>3, let$ $a=(p-1)![1+1/2+...+1/(p-1)]\in N $ Then prove that p|a and also $ p^2|a$ Thanks in advance!
0
votes
0answers
66 views

How can I check these equations if they have a solution?

I have two equations which are: $p^3+k\equiv0 (mod \quad h) $ and $(3p^2+3mp+m^2)m\equiv 0(mod \quad h)$ where $k,h,m >0$ and $p\ge0$ and $h\nmid m$ I need to show for given k,m,h and for all ...
0
votes
1answer
34 views

Compute the product of digits of P

Give $P$ a integer number where $$P=2^{3^{4^{5^{\dots1000}}}}$$ Then Compute The product of dígits of $P$ Compute $P\pmod{5}$ for The segond i think its will be something like ...