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

0
votes
2answers
37 views

Verifying integer solutions to linear equations

Suppose I have the equation $B = \frac{8A - 29}{27}$, where $A$ and $B$ are integers. Then $27B = 8A - 29$, and so we have the linear Diophantine equation $8A - 27B = 29$. Using the extended ...
5
votes
1answer
284 views

Why did Fermat care about characterizing primes on the form $p=x^{2}+ny^{2}$?

Im currently trying to figure out the genesis of quadratic reprocity by using Cox and Lemmermeyers books. I also got a copy of some works of Fermat but it is in German. It seems like there is some ...
0
votes
1answer
106 views

Listing the elements of $U(\mathbb{Z}_{54})$.

The set of all integers modulo $q$ is denoted by $\mathbb{Z}_q$. When equipped with multiplication modulo $q$, has the structure of a commutative monoid, the identity element being equivalence class $...
0
votes
2answers
39 views

Congruence with binomial

I tried to prove this by induction on $k$. But I did not manage Let $p$ be a prime. For every $k\in\{0,\cdots,p-1\}$, one has $$\binom{p-1}k\equiv(-1)^k\pmod p.$$ By Wilson theorem, it suffices to ...
3
votes
1answer
94 views

Prove that a square of a positive integer cannot end with $4$ same digits different from $0$

Prove that a square of a positive integer cannot end with $4$ same digits different from $0$. I already proved that square of positive integer cannot end with none of digits $1,2,3,5,6,7,8,9$ using ...
0
votes
1answer
358 views

Use Pohlig-Hellman to solve discrete log

We have $$7^x = 166 \pmod{433}$$ I need to find $x$ using the Pohlig-Hellman algorithm.
2
votes
1answer
83 views

How to find fast modular exponentiation?

I need to find $$5448^{5^3} \pmod{11251}$$ and $$6909^{5^3} \pmod{11251}$$ fast? I couldn't calculate it with normal tricks.
1
vote
1answer
65 views

Finite fields and arithmetic

For every prime number $p$ and every positive integer $k$, there is a field with exactly $p^k$ elements. When $k=1$, it's just the integers$\bmod p^k$, and when $k>1$, it's not. So if I want the ...
3
votes
1answer
103 views

Diophantine equation involving factorial …

Question . Find all positive integer solutions to the equation below , $$(n-1)!+1=n^m$$ (i)observe that $n>1$ and $n$ is a prime number (if not we can choose a prime number $p<n$ such that $p|n$ ...
4
votes
2answers
83 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
39 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
57 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
136 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
89 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?
4
votes
3answers
140 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 6^{...
0
votes
1answer
55 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 to ...
2
votes
1answer
331 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
5
votes
2answers
785 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
37 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
278 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
124 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
70 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
33 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
133 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 (\mathbb{Z}/...
0
votes
3answers
76 views

Sum of odd numbers is odd if each of the natural numbers is odd

Prove that the sum of an odd number of natural numbers is odd if each of the natural numbers is odd. Here's what I tried already but it didn't work: $\sum_{i=0}^n i = 2n-1$ but when I use ...
1
vote
2answers
49 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
41 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
124 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
119 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
40 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
88 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 $1$...
7
votes
1answer
161 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
65 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
43 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
49 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
37 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
60 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
36 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
56 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
49 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 ...
3
votes
1answer
47 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 ...
5
votes
3answers
136 views

Prove that, $(2\cdot 4 \cdot 6 \cdot … \cdot 4000)-(1\cdot 3 \cdot 5 \cdot …\cdot 3999)$ is a multiple of $2001$

Prove that the difference between the product of the first 2000 even numbers and the first $2000$ odd numbers is a multiple of $2001$. Please show the method. I have started with the following ...
0
votes
2answers
56 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
41 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?
0
votes
0answers
23 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!
2
votes
1answer
48 views

How to solve the congruence $ x^4 + x + 3 = 0 \pmod{3^3}$?

$$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
66 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 ...
1
vote
0answers
268 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
41 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
59 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$ ...