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
4answers
47 views

inverse modulo, modulo arithmetic

I was given following example in the book, however I am not sure how can the result of 27 be calculated. I realise that -13 + 40 gives 27, however how 27 ≡ −13 (mod 40) is the same as 3·(−13) ≡ 1 (mod ...
12
votes
7answers
1k views

How do I prove that there infinitely many rows of Pascal's triangle with only odd numbers?

This is exercise number $59$ from Chapter $2$ of Hugh Gordon's Discrete Probability. Show that there are infinitely many rows of Pascal's Triangle that consist entirely of odd numbers. ...
4
votes
6answers
137 views

Why is a negative modulo a negative, a negative?

I have understood that $-340$ mod $60$ = $20$ because $-6 \times 60$ = $-360$ is smaller than $-340$. Can someone explain why $-340$ mod $-60$ = -$40$?
4
votes
1answer
75 views

Is $((a \mod n) + (b \mod n) ) = (a + b) \mod n$?

As we know $(a + b) \mod n = ((a\, \bmod\, n) + (b\, \bmod\, n))\, \bmod\, n$ Is their reversal also true like this $((a \mod n) + (b \mod n)) = (a + b) \mod n$. If not then what could be its ...
0
votes
1answer
26 views

Quadratic congruences in which modulus is divisible by constant term

There are two similar congruences: $$ x^2-6x\equiv16\pmod{512}\\ y^2-y\equiv16\pmod{512} $$ It is easy to see that the $\gcd$ of all three parts in both of them is $16$, $x$ and $x-6$ are even and one ...
3
votes
1answer
50 views

Question about how to prove $x^5\equiv x \pmod {10}$ [duplicate]

I was trying to prove why $x^5\equiv x \pmod {10}$ for all natural numbers $x$. I saw a proof where they applied Euler's theorem to show this. They said that the totient function for $10$ is $4$. ...
3
votes
3answers
197 views

How to divide natural number N into M nearly equal summands?

How to divide natural number N into M nearly equal summands? For example, to divide 20 by 13, in geometric representation, I should get How to generate the sequence above? What is the name of ...
2
votes
1answer
67 views

Cryptography, discrete mathematics

I have got following example at the lecture, however we went through it quite fast. I understand the calculation of the following inverse modulo: 7 · 103 = 1 (mod 120). However here I am puzzled ...
0
votes
2answers
27 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
263 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
103 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
30 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 ...
0
votes
0answers
26 views

Ring structure of tuples mod k

Consider a vector of n integers $$A= a_1, a_2, ... a_n$$ Such that for another vector $$B= b_1,b_2... b_n$$ $$AB^T \equiv 0 \mod k$$ For an integer k. I was playing around with these structures ...
0
votes
1answer
77 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
69 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.
0
votes
1answer
59 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
47 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
51 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
41 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
51 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
36 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?
3
votes
3answers
73 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
45 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
61 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
252 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
30 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
257 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
90 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
63 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
30 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
37 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
41 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
39 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
23 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
25 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
27 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
50 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
126 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
53 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
32 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
35 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
31 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
11 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
55 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
31 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
21 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
24 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
40 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
42 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) ...