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
vote
1answer
34 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}} ...
3
votes
2answers
60 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
52 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
2answers
40 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
55 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
24 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
36 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
28 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
36 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
45 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
32 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
45 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
25 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
35 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$.
3
votes
0answers
64 views

Fibonacci Quadratic Residue

After some research I have came up with a conjecture on fibonacci quadtratic residue: ...
0
votes
1answer
43 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
54 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
39 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
31 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
34 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 ...
2
votes
2answers
171 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
50 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
48 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 ...
2
votes
1answer
32 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
90 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
148 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 ...
2
votes
1answer
48 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
35 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
63 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: ...
0
votes
1answer
51 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
34 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
36 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
77 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
25 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 ...
1
vote
8answers
158 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: ...
3
votes
3answers
57 views

Is $(-1)^{1/8} + (-1)^{7/8}$ ever a value whose real component is $0$?

Is $$(-1)^{1/8} + (-1)^{7/8}$$ ever a value whose real component is $0$? Is this ever true in modular arithmetic, hypercomplexes, and/or both?
4
votes
3answers
591 views

Prove that every prime larger than $3$ gives a remainder of $1$ or $5$ if divided by $6$

Can we prove that every prime larger than $3$ gives a remainder of $1$ or $5$ if divided by $6$ and if so, which formulas can be used while proving?
0
votes
1answer
32 views

Solving a system of modular equatios

Edit: I can't actually see how Chinese remainder theorem works here, if we had only $x$ on the left of each equation I can see how I could work it, but we don't. I can't seem to reduce it down to just ...
3
votes
3answers
42 views

If $n > 2$, prove that the order of the multiplicative group of units modulo n, $U_n$, is even.

I'm struggling with this. I know it is going to use Lagrange's Theorem so this is what I have so far: Suppose $|U_n| = k$ This implies $a^k = 1$ for all a in $U_n$ and $|a|$ divides $k$. Now, what ...
0
votes
1answer
16 views

Remainder operation in terms of the floor function

I came across this identity $$a\bmod{n}= a - \left\lfloor \frac{a}{n} \right\rfloor \times n$$ I see that it works, but I'm struggling to prove it, so I thought I would ask you guys.
1
vote
1answer
47 views

Integer solutions of the equation $a^{n+1}-(a+1)^n = 2001 $

I am doing number theory and I came across that question $a^{n+1}-(a+1)^n = 2001 $. Find the integer solutions and show that they are the only solution. I really tried hard but i am nowhere near ...
1
vote
1answer
34 views

Proof on Divisibility of Binomial Coefficients

Prove that $\exists \ i$ $(0 \lt i \lt n)$ such that $$ n \nmid {n \choose i} $$ $\forall \ n$ such that $n \gt 0$ and $n$ is a composite Number.
0
votes
2answers
18 views

If $c \not\equiv 0 \pmod p$ then $\forall a \not\equiv 0\ \exists b \not\equiv 1$ so $c+a\equiv ab \pmod p$

Im looking for a correct argumentation of why the folowing holds, any help would be great: For $p$ prime, if $c \not\equiv 0 \pmod p$ then $\forall a \not\equiv 0 \pmod p ~\exists b \not\equiv 1 ...
4
votes
0answers
32 views

Subsets of cyclic group with distinct pairwise differences

Given a number $m\in\mathbb N$, let $\mathbb Z_m=\{0,1,\dots,m-1\}$ denote the ring of integers modulo $m$ (although we won't need multiplication, so any cyclic group of order $m$ will do). Given a ...
2
votes
3answers
83 views

Find the remainder of $40^{314}$ divided by 91.

Here's what I have so far. $$x \equiv 40^{314} \mod{91}$$ $$\Rightarrow$$ $$x \equiv 40^{314} \mod{7}$$ $$ x \equiv 40^{314} \mod{13}$$ Then by FLT, $$40^6 ≡ 1 \mod{7}$$ $$40^{12} ≡ 1 \mod{13}$$ ...
0
votes
1answer
19 views

Let $m=p^t$ where p is a prime. Prove that $a^{\phi(m)+t} \equiv a^t \bmod{m}$ for ${\bf all}$ integers a

So, I was thinking that $a^{\phi(m)}\equiv 1 \bmod{m}$, thus when multiplying $a^t$ on both sides, we get that $a^{\phi(m)+t} \equiv a^t \bmod{m}$. What is throwing me off is the all integers a part.
4
votes
4answers
87 views

Prove that $a^7-a$ is divisible by 168 when a is odd

so I saw a similar question that proves $168\mid(a^6-1)$ when $(42,a) = 1$. But for this problem I was not given that gcd$(a,42)=1$. When I factor out a I get $168\mid a\cdot(a^6 - 1)$ and since $a$ ...