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
votes
3answers
85 views

mod of minus power 1

I am fully aware on how to perform mod calculation. The issue now is that when I have this $2^{-1} \bmod 10$. How to do this? Is there any formula for this?
0
votes
1answer
55 views

Solving two variables system equations with parameter above $\mathbb{Z}_7$

Let: $$(1+5a)x +y = 1$$ $$a^2x + y = 2$$ Eliminating the $y$ variable we have: $$(-a^2 +5a +1)x = 6$$ Now, I should have find $y$ such that $(-a^2 +5a +1)y = 1$, but obvoiusly I can't do that ...
2
votes
3answers
127 views

Modular congruence, splitting a modulo

I can't find out, how to solve this. Will you give me some advice what to do in 4th step? Lot of thanks. This is my example: $7^{30}\equiv x\pmod{ 100}$ I want to compute it this way. These are my ...
1
vote
1answer
75 views

What does $ a \pmod b$ mean?

I am having little trouble in what a$mod$b means. I under stand that if $a\equiv b\pmod n$, then n divides (a-b). But I do not understand what does it mean by $b\pmod n$. One the thing I can think of ...
1
vote
1answer
48 views

Primitive roots used to work out $x^7 \equiv 5 \pmod {11}$

I have a workbook question that doesn't have any example solution, that is as follows: Primitive roots used to work out $x^7 \equiv 5 \pmod {11}$ Now I can see $\phi(11)=10$ and $2$ has order $10$ ...
3
votes
3answers
66 views

Solve for x in $5 \equiv 128x$ (mod 59)

I'm just running a blank here in review for finals and cannot seem to figure it out for the life of me. I want to say that you must use extended euclidean algorithm somehow, and I checked that the ...
2
votes
2answers
377 views

Show that an integer of the form $8k + 7$ cannot be written as the sum of three squares.

I have figured out a (long, and tedious) way to do it. But I was wondering if there is some sort of direct correlation or another path that I completely missed. My attempt at the program was as ...
1
vote
3answers
132 views

Verify that $4(29!)+5!$ is divisible by $31$.

Verify that $4(29!)+5!$ is divisible by $31$ I know I have to use Wilsons theorem: $(p-1)!=-1\pmod p$ but I'm not really sure how to apply this theorem. Step by step explanation please? Thank you!
0
votes
1answer
61 views

What day of the week was it on this date in the year 1000?

Don't forget that every year divisible by 4 is a leap year, except that century years are only leap years if divisible by 400 (e.g., 2000 was a leap year, but 1900 was not). Another question in my ...
0
votes
0answers
66 views

Why there is no zero-divisors modulo a prime.

Let us say that an integer $k$ where $0< k < m$ is a zero-divisor mod $m$ if $kn \equiv 0 \pmod{m}$ for some $n$ with $0 < n < m$. Prove the following: If $m$ is prime then no integer $k$ ...
0
votes
0answers
40 views

About gaussian integers and orders.

I noticed $(1+i)^{16}= 256$ so $(1+i)^{16} - 1$ is a multiple of $17$. So $(1+i)^{16} - 1$ is a multiple of $(1+4i)$ or $(1-4i)$. $(1+i)^{|1+4i|}$ is congruent to $1$ or $i$ mod $(1+4i)$. I think . ...
0
votes
1answer
17 views

Solving for modular expression?

I stuck somehow on repetition old math exercises...could someone explain the following expression: $(n!-1)$ mod $ n $ Thanx
0
votes
3answers
52 views

Modular equations, find x

Problem: Find an integer $x$ such that $x = 5\pmod 8, x = 3 \pmod 9, x = 4 \pmod 7$. Attempt: By the Chinese Remainder Theorem " Suppose $a_1,a_2,...a_k$ are integers pairwise relatively prime ...
1
vote
3answers
56 views

Modulo Inverse using extended euclidean

My aim here to learn the Chinese Remainder theorem. But am stuck at finding the inverses. Suppose we have 42 mod 5, but according to the CRT question, we must make it 42 * x congruent to 1 (mod 5) ...
0
votes
1answer
58 views

Given the gcd(a, b) = 1, prove x = y mod a & x = y mod b iff x = y mod a*b

I am thinking that this is a variation of the Chinese Remainder Theorem as the iff qualifies that this set of equations is not exactly the definition of the Chinese Remainder Theorem, leading me to ...
2
votes
2answers
94 views

Modulus simplification $(mn) \bmod d = ab$?

I have a modulus question that needs me too prove whether two different statements are true or false. The information I have been given is that: \begin{align} m \bmod d &= a\\ n \bmod d &= ...
1
vote
2answers
204 views

find smallest value of N such that N mod 10 = 9 , N mod 9 = 8 and so on

find the smallest value of N such that N mod 10=9, N mod 9 = 8, N mod 8 = 7, N mod 7 = 6 and so on till N mod 2 = 1 .
0
votes
2answers
23 views

For what values of b does the following system of modular equations have a solution?

$$x \equiv b (100)$$ $$x \equiv b^2 (35)$$ $$x \equiv 3b - 2 (49)$$ If I was pressed for an answer I would say this system was unsolvable. If $x \equiv b(100)$ the $x = b + 100t$. Then $b + 100t ...
0
votes
1answer
26 views

Linear equation with residue classes

I'm having a hard time solving an exercise that seems fairly easy: Given a linear map $$ f: (Z/5)^2 \mapsto (Z/5)^2 $$ and $$ f(\bar{2}, \bar{3}) = (\bar{1},\bar{1})$$ $$f(\bar{1}, \bar{4}) = ...
0
votes
1answer
40 views

Why is $U(12) = U_{4} (12) ~ U_3(12)?$

Why is $U(12) = U_{4} (2)~ U_3(12)$ Attempt: Any subgroup $U_k(n) = \{x \in U(n)~~|~~x \mod k=1 , k ~|~n \}$ Hence : if $U(12) =\{1,5,7,11\}$ then : $U_4(12) =\{1,5\}$ and $U_3(12)=\{1,7\}$ We see ...
0
votes
1answer
37 views

Can diagonalization mod p be generalized to diagonalization mod n?

When you diagonalize a matrix $A$, your $D$ matrix will be the similar to if you diagonalized $A$ mod $p$ (but $D$ will also be mod $p$ in this scenario). I'm having a brainfart moment here. Does $p$ ...
0
votes
1answer
92 views

Regarding Gaussian integers and primitive roots.

Can modular arithmetic be set up using gaussian integers instead of (non-complex) integers? If so is there an analogue of 'primitive roots' with Gaussian integers?
0
votes
1answer
28 views

Find one sum in the function of another sum only

Let $S = s_1 + s_2 + ... + s_n$, with $s_i \in N$. Let $M =(p_1*s_1 + p_2*s_2 + ... + p_n*s_n) \bmod{p_{n+1}}$, where $p_i$ indicates $i$-th prime. Find $M$ in the function of $S$ only. Source: ...
0
votes
1answer
60 views

Chinese Remainder Theorem, remainder when dividing by a polynomial

I was reading throught this question: Give the remainder of x^100 divided by (x-2)(x-1) and I couldn't get the same expression as the answers. I have a basic understanding of modulos and Chinese ...
1
vote
1answer
58 views

$|p+1|=p^{n-1}$ in $\left( \mathbb{Z}/p^n \mathbb{Z} \right)^\times$

I want to solve the following exercise from Dummit & Foote's Abstract Algebra: Let $p$ be an odd prime and let $n$ be a positive integer. Use the Binomial Theorem to show that $(1+p)^{p^{n-1}} ...
4
votes
2answers
76 views

Help with proving that $A^p \equiv A$ mod $p$ does not mean that $A$ is diagonalizable

I'm working on a matrix extension of Fermat's Little Theorem, but I'm stuck on trying to show that if $A^p \equiv A$ mod $p$, then $A$ does not have to be diagonalizable. Any help would be ...
1
vote
2answers
137 views

prove a=b (mod n) then ra=rb(mod n)

I seem to not be able to find anything about these type of questions, could anyone help me prove the following question. Start up on how to do the question would be appreciated too! $a≡b \mod n$,then ...
1
vote
1answer
42 views

What are the solution for this system?

I have a congruence system of equations : $a\equiv-1\pmod 7$ $a\equiv0\pmod{13}$ what are the possible values for $a$ knowing that $a\in \mathbb{Z}$. i tried to put $13k$ in the first equation and ...
0
votes
2answers
1k views

Use Euclid's Algorithm to find the multiplicative inverse

Use Euclid's Algorithm to find the multiplicative inverse of $13$ in $\mathbf{Z}_{35}$ Can someone talk me through the steps how to do this? I am really lost on this one. Thanks
1
vote
1answer
27 views

Factoring in terms of Irreducibles

Factor the polynomial $x^5 + 2x^3 + 3x^2 + 1$ as a product of irreducible polynomials in $\mathbb{Z}_5[x]$. My thoughts: I know what the definition of an irreducible function is but as far as methods ...
1
vote
1answer
47 views

How to give irreducible factorization in $\mathbb{Z}_5$?

I have this polynomial: $$f=x^5+2x^3+4x^2+x+4$$ How can i find the irreducible factorization(in $\mathbb{Z}_5$)?I can find the roots easily but thats not enough.
1
vote
1answer
40 views

Find a polynomial mod $n$ injective on a given set

This question is inspired by this challenge on CodeGolf.SE, in which the goal is to create a hash function with specified collisions. I thought a polynomial over the integers mod $n$ might be a nice ...
0
votes
2answers
37 views

How can I find $x$ such that $ax \equiv 1 \pmod{bx+c}$, given $a,b,c$?

Everything I've read about modular arithmetic generally concerns doing things in some "mod m" world where "m" is some constant. But I'm perplexed how to tackle modular arithmetic problems where the ...
1
vote
2answers
42 views

$a_3$, $a_5$ and $a_0$ terms are required?

We have an arithmetic sequence $a_n>0$ and it's increasing. and we've two systems of equations: $a_4=15$, $m+d=21$ whereas $m=lcm(a_3,a_5)$, $d=\gcd(a_3,a_5)$. What are the values of $a_3$, ...
1
vote
3answers
47 views

How to prove that $\gcd(\alpha,\beta) = \gcd(\beta,10)$?

We have $\alpha=2n^3-14n+2$ and $\beta=n+3$, How can we prove that the $\gcd(\alpha,\beta)=\gcd(\beta,10)$, and what are the possible values for this $\gcd$.
0
votes
2answers
43 views

Let $p$ be an odd prime. Prove that if $a\equiv b\pmod{p}$, then $a^p\equiv b^p\pmod{p^2}$

Let $p$ be an odd prime. Prove that if $a\equiv b\pmod{p}$, then $a^p\equiv b^p\pmod{p^2}$ I know how to prove this if we are given $a^p$ is congruent to $a$ mod p, but not when we start with this.
1
vote
5answers
51 views

If $x\equiv2\pmod{3}$ prove that $3|4x^2+2x+1$

I've tried many different things to get a factor of $k-2$ but keep failing. If $x\equiv2\pmod{3}$ prove that $3 \mid 4x^2+2x+1$
0
votes
1answer
31 views

Quick Modular Property Help

Is this property always true? if $x \mod y = z$, then $ax \mod ay = az$? for all intergers $x,y,z,a$.
1
vote
1answer
90 views

Diffie–Hellman key exchange

Today I have learned about primitive roots, as part of my study about Diffie-Hellman, This is the formula: G(generator), P(prime), A(side A), B(side B) A = G^A MOD P B = G^B MOD P AS is a secret ...
0
votes
1answer
32 views

what are the values of m when $m(3^{2m}+3) \equiv 0 \mod 28$?

Can you help me with this problem. I want to know what are the values of m which makes $m(3^{2m}+3) \equiv 0 \mod 28$.
4
votes
0answers
101 views

Fibonacci Quadratic Residue

After some research I have came up with a conjecture on Fibonacci quadratic residue: $F(x)^2 mod F(y)$ = { if y is even: $(F(|x-y|)^2$ } { if y is odd: $-(F(|x-y|)^2$ } for ...
0
votes
1answer
46 views

For every positive integers $a$ and $n$, is it true that: $a^{n−1} \equiv 1 \pmod n \iff \gcd(a,n) = 1$?

Based on Fermat's little theorem or on Euler's theorem, is the statement $$a^{n−1} \equiv 1 \pmod n \iff \gcd(a,n) = 1$$ true for every positive integers $a$ and $n$?
3
votes
2answers
84 views

Conjecture on twin primes

Let $p$ and $p+2$ be both prime. I conjectured (with my ignorance) that $$p^{\frac{p+1}{2}}\equiv -1\mod{(p+2)}$$ except for $p=17,41,71,137, 191, 239....$ I verified this on Mathematica. So for ...
1
vote
1answer
28 views

What do we know about a % b % c?

That is, what can we say about chained application of the modulo operation? E.g., are there any theorems for certain values of a,b, and c s.t. (a % b % c) == (a % bc), or something similar? The only ...
0
votes
1answer
42 views

Using Fermat's Little theorem to prove that $12\mid n^2-1$ when $(n,6)=1$

I need help proving the first one via Fermat's little theorem. I need a hint, or a good starter!
1
vote
1answer
45 views

Prove that a number is prime iff the factorial of its predecessor is the predecessor of one of its multiples.

I have tried to prove this via algbra but I got stuck. I was wondtering if there is any other way to prove this, like with a theorm. Any ideas are welcome!
0
votes
1answer
51 views

Multiplicative inverses and co-primes

I'm working out some examples on multiplicative inverses. I understand how to solve for a multiplicative inverse using the Extended Euler's algorithm, but I don't understand the principles which ...
3
votes
2answers
1k views

Last digits, numbers

Can anyone please help me? 1) Find the last digit of $7^{12345}$ 2) Find the last 2 digits of $3^{3^{2014}}$. Attempt: 1) By just setting the powers of $7$ we have $7^1 = 7$, $7^2=49$, $7^3=343$, ...
1
vote
2answers
188 views

How to use Fermat's little theorem to find $50^{50}\pmod{13}$?

I don't understand how to use Fermat's little theorem to find remainders e.g if we are asked to find remainder of $50^{50}$ on division by $13$, what is a and what is $p$ in the formula? Also I ...
1
vote
2answers
56 views

Show $4x^3 + y^3 = 792,864,313,578,917,724,246$ has no solution for $x, y \in \mathbb{Z}$.

I think it involves something about looking at the last digits of the number and/or modular arithmetic but I don't remember how to do this. Help?