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
1answer
54 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
90 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
197 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
25 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
36 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
82 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
58 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
57 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
128 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
46 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
38 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
42 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
87 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
97 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
83 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
41 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
43 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
955 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
172 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
54 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?
0
votes
1answer
52 views

Galois field splitting a polynomial

Can someone explain to me how i would go about doing a problem like this? I don't really know where to start. GF refers to a Galois field. I'm struggling to even understand exactly what they want me ...
-1
votes
2answers
94 views

Showing that $x^{11} \equiv 5 \pmod{47}$ has only solution $x \equiv 15$.

I don't understand the proof. Where did they get the first line from, i.e., $21 \times 11=1+5 \times 46$? Fermat's theorem in my view is $a^{46} \equiv 1 \pmod {47}$.
2
votes
1answer
49 views

Euclidean Algorithm for Modular Inverse, with negative numbers

I might be on to something quite simple which I'm failing to see, while calculating modular inverses. For example, calculating 7x = 5 (mod 12) Which is the same as saying: 7x - 5 = 12k Which ...
0
votes
4answers
213 views

Proving Congruence for Numbers

I am working on a problem I am pretty close to solving but I can't figure out the last part. I used some algebraic manipluation to break the problem down. The problem is: Show that the following ...
6
votes
1answer
164 views

Congruences and prime powers

I have just a small question that probably is not hard to answer, but I could not find and elegant solution to this question. Let $p$ and $q$ be prime numbers. $$5^q\equiv 2^q \pmod p$$ $$5^p\equiv ...
3
votes
2answers
66 views

Modular arithemtic and CRT

I'm trying to solve the following congruence: $71x-1 \equiv 0 \pmod{59367} $ Given that $59367=771 \times 77$, I have previously solved that: $71x \equiv 1 \pmod{771}$ such that $x=-76$ $71x ...
0
votes
0answers
38 views

If $k\le n$ and $k$ is relatively prime to $n$, there exists a prime $p$ such that $p \equiv k \mod n$.

I need to use this result in a step of a proof, but I am for some reason unable to justify it. It seems to be true, after trying some examples, but I am not sure why. If $1 \le k\le n$ and $k$ is ...
4
votes
2answers
71 views

Why can't we have an $y$ such that $xy\equiv 1\; (mod\; n)$ when $n$ is not prime?

I'm reading Avner's Fearless Symmetry: Here he says that we can only have the cancelation law if the modulus is prime: I got curious with the statement and then I kept reading the chapter: ...
1
vote
1answer
124 views

Does Fermat's Little Theorem apply to matrices?

I'm working on a problem involving applying FLT to matrices, so any information about how to do this or prove this is true would be helpful. I've been doing some research and experimenting a little, ...
0
votes
1answer
42 views

Modular Arithmetic

I am doing some exam preparation and can't figure out how to do the following question. It seems to be a regular question and was wondering if anyone who could tell me an approach to this style of ...
0
votes
3answers
45 views

Modular Arithmetic

I am doing some exam preparation and can't figure out how to do the following question. It seems to be a regular question and was wondering if anyone who could tell me an approach to this style of ...
1
vote
2answers
124 views

Last Two Digits Problem

I'm trying to find the last two digits of ${2012}^{2012}$. I know you can use (mod 100) to find them, but I'm not quite sure how to apply this. Can someone please explain it?
0
votes
1answer
39 views

Question regarding solving a modulo equality

Two Equations: ab % c = d (ci + d) % c = d, i $\in \mathbb N$ I want to solve for b given the above two equations with a, c, and d known. ab = ci + d b = (ci + d) / a i = (k + an), n $\in ...
4
votes
8answers
229 views

Calculate the last digit of $3^{347}$

I think i know how to solve it but is that the best way? Is there a better way (using number theory). What i do is: knowing that 1st power last digit: 3 2nd power last digit: 9 3rd power last digit: ...