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

3
votes
3answers
84 views

Show that $a - b \mid f(a) - f(b)$

I have seen this lemma elsewhere. Suppose $A$ is a domain, and $f \in A[X]$. Prove that $$a - b \mid f(a) - f(b)$$ I need to prove this. $$f(a) - f(b) \equiv 0 \pmod{a-b}$$ basically. Let, $a ...
3
votes
1answer
42 views

Do there exist Artificial Squares?

Denote an artificial square E as a number: $$E \in \Bbb{N}| \lnot (\exists y \in \Bbb{Z} | y^2 = E) \land (For \ each \ w \in \Bbb{Z} \ \exists a_w | a_w^2 \equiv E \ \pmod w) $$ In other words ...
0
votes
0answers
19 views

Trying to determine the relationship of m and n in a Casting Out m under base n

While exploring $\mathbb{Z/n}$ I stumbled upon this It explains that Casting Out Nines works because our common counting system is decimal and thus there exist a congruence relation as follows ...
0
votes
2answers
46 views

Why is $-9 \cdot 26 \equiv -1 \cdot 26 \mod 103$?

Instead of multiplying $-9$ and $26$ out, the professor got rid of a multiple of $9$ immediately before actually performing the next modular arithmetic step. What justifies this step of getting rid of ...
2
votes
2answers
96 views

Solving an equation $\pmod {13}$

Suppose: $$1 + \frac12 +\frac13 + \dots + \frac1{23} = \frac{a}{23!}$$ I would like to find $a \pmod {13}$. My attempt: I'm attempting to use Wilson's theorem which states: $$(n-1)!= -1 \pmod n$$ ...
0
votes
1answer
31 views

Polynomial long division modulo 7,

I need to determine the quotient and remainder using polynomial long division in $Z_7[x]$. I'm not sure how to tackle it with the polynomials given, and I'm growing frustrated by it. I need to divide ...
1
vote
3answers
35 views

Modular arithmetic $x \equiv 17^{12} \pmod {11}$

I'm trying to evaluate $x \equiv 17^{12} \pmod {11}$ using modular arithmetic, but I'm a bit lost. I'd really appreciate a step-by-step on how to do it. Thanks!
1
vote
2answers
45 views

If $n-1$ is prime show it is relatively prime.

If $n$ is a natural number, and $n-1$ is prime, show that, $$\gcd(n-1, (n-2)!) = 1$$ I tried: $$= \frac{(n-2)(n-3)(n-4)...1}{(n-1)}$$ But what to do?
2
votes
2answers
35 views

Suppose that $gcd(a,n)= 1$. Prove that $a^m \equiv 1 \pmod n$ iff $ord(a,n) \mid m$

Here is my attempt. Suppose we have $a^m \equiv 1 \pmod n$ and assume that $ord(a,n) = k$ (order of $a)$ and so since $k = ord(a,n)$ it follows that $k \leq m$ . Now if $k = m$ then we are done but ...
2
votes
3answers
29 views

factoring zero in modulo n

Let $m,n\in \mathbb{N}$. How many different classes $\overline{y}\in\mathbb{Z}_n$ are there, so that $$\overline{m}\cdot \overline{y}=\overline{0}$$ Each element is either invertible or a factor of ...
3
votes
1answer
41 views

Arithmetic modulo primes task

I'm dealing with a problem here. The problem is as follows: There is a set $Z_p=\{0,1,2,3,...,p-1\}$ where $p$ is a prime. From this set we form a new set $B=\{x+x^{-1}\mid x\in Z_p\}$, where the ...
1
vote
2answers
60 views

Q: simple modular arithmetic

I am trying to solve a programming problem but am stuck on some modular algebra. The equation I am trying to solve boils down to $$a \equiv (b + cx)\pmod {10^9+7}$$ where I know a, b, and c and need ...
0
votes
1answer
30 views

How to show that $pm/pn=m/n$ and that $pm \bmod pn = p(m \bmod n)$?

I'm sure I'm overly thinking this but I'm stuck and I need help just starting the following problem: Show that for any natural number $m$, any positive natural number $n$ & any positive natural ...
0
votes
2answers
65 views

Proving $2$ generates $(\mathbb{Z}/19\mathbb{Z})^*$ by only looking at a few powers

So I'm first asked to compute, mod 19, the powers of 2, $$2^{2},2^{3},2^{6},2^{9}$$ which I compute as $$4,8,7,18$$ respectively. I'm then asked to prove that 2 generates ...
0
votes
0answers
25 views

Another question related to the sum-of-divisors function

If ${q^k}{n^2}$ is an odd perfect number where $q$ is prime with $q \equiv 1 \pmod 4$ and $\gcd(q,n)=1$, then $\sigma(q^k)/n \neq \sigma(n)/q^k$, where $\sigma$ is the classical sum-of-divisors ...
-1
votes
1answer
74 views

How to solve a quintic congruence equation? [duplicate]

My textbook has this quadratic equation that I have to solve, any ideas how I could show that? $$15 | (21n^5+10n^3+14n),\;\forall n\in\mathbb{Z}$$
1
vote
1answer
41 views

If $p=4k+3$ then $\mathbb{Z}_{p}[\sqrt{-1}]$ is a field

I want to know about an elementary proof (at the level of elementary number theory) of the fact If $p$ is a prime number of the form $4k+3$ then $\mathbb{Z}_{p}[\sqrt{-1}]$ is a field where $$ ...
3
votes
3answers
80 views

primitive roots problem. that integer n can never have exactly 26 primitive roots.

Show that no integer $n$ can have exactly 26 primitive roots. I know that if $n$ has primitive roots then it has exactly $\phi(\phi(n))$ primitive roots. I think the proof has to use contradiction. ...
1
vote
1answer
31 views

Modular Arithmetic - Finding q

I am having trouble comprehending the following problem: In mod $n$ arithmetic, the quotient of two numbers $r$ and $m$ is a number $q$ such that $mq = r$ mod $n$. (The author mentioned before that ...
2
votes
3answers
79 views

Negative modulus

In the programming world, modulo operations involving negative numbers give different results in different programming languages and this seems to be the only thing that Wikipedia mentions in any of ...
0
votes
1answer
15 views

Modular Simultaneous Equations

Can someone please help me out, as normally i am only use to dealing with one unknown for modular simultaneous equations. The question is, solve : $x + 2y \equiv 3 \mod 7$ $3x+ y \equiv 2 \mod 7$ ...
5
votes
2answers
139 views

A prime number generator algorithm based on $x^2+(x-1)^2$ that generates only primes

I think I could have found a prime number generator algorithm, but still I am not very sure, maybe this is an already known property of perfect square numbers, maybe not, but it looks amazing and I ...
1
vote
1answer
24 views

General divisibility test for $p\in\mathbb{N}$, $p$ prime

I have read the recursive divisibility test of number $n\in\mathbb{N}$ as $$f-Mr,$$ where $f$ are the front digits of $n$, $r$ is the rear digit of $n$ and $M$ is some multiplier. And I want to see ...
2
votes
0answers
33 views

Number Theoretic Transform (NTT) to speed up multiplications

I recently heard that the Number Theoretic Transform (NTT), which is a specialization of Fast Fourier Transformation (FFT) over the ring modulo an integer, can be used to speed up certain ...
0
votes
1answer
23 views

Discrete Math- Modular Congruence

The problem is asking to find c given that- c ≡ 13a(mod19) and the variable a ≡ 11 (mod19). I've tried to solve this using algebra and using the theorems but I can't seem to work it out. Any ...
1
vote
1answer
42 views

Proof with congruence and primes. $(p\mid a^2+b^2)(p\not\mid a,p\not\mid b)\implies \exists c\in\mathbb Z( c^2=-1\pmod {p})$.

The statement is as follows: $ p|(a^2+b^2), p\not\mid a, p\not\mid b$ . Prove there exists an integer $c$ such that $c^2\equiv -1 \pmod p$. What I tried to do is apply definition of congruence to ...
1
vote
0answers
28 views

Simplified Exponent in $\bmod$ equation

I am trying to simplified the following expression: $$\left(y^m\right)^{x} \bmod p$$ In my case, I can only solve $(y^x) \bmod p$ first without prior knowledge of $m$. Eventually, my answer should ...
1
vote
2answers
62 views

If every pair of congruence equations admits solutions, then the entire system admits solutions

Let a system of three linear congruence equations in integers be given; \begin{cases}x\equiv b_1\mod c_1\\ x\equiv b_2\mod c_2\\ x\equiv b_3\mod c_3\\ \end{cases} with $c_1,c_2,c_3\in\mathbb ...
0
votes
2answers
37 views

AMC 12A, problem with days

In year N, the $300th$ day of the year is a Tuesday. In year $N+1$, the $200th$ day is also a Tuesday. On what day of the week did the $100th$ day of year $N - 1$ occur? (2000 AMC 10 #25) The ...
0
votes
1answer
19 views

Converting a complicated congruence equation

From: $$5991x \equiv -289 \pmod{2014}$$ I saw people converted this to: $$3x \equiv 17 \pmod{2014}$$ But how? My attempt: $$5991x \equiv -289 \pmod{2014} \equiv 1725$$ $$1997x \equiv 575 ...
0
votes
1answer
47 views

If $x^4\equiv86\mod{125}$, how to find $x$?

If $x^4\equiv86\mod{125}$, how to find $x$ ? We had a Proposition that; (only $(ii)$ is relevant in this example) $\textbf{Questions}$ $1)$ (In the $9$th line of the example) Why must be $b$ ...
2
votes
8answers
102 views

How to show $n^5 + 29 n$ is divisible by $30$

Show that $n^5 + 29 n$ is divisible by $30$. Attempt: $n^4 ≡ 1 \pmod 5$ By Fermat Little Theorem
1
vote
0answers
37 views

Show that if $p$ is prime , then $a^p \equiv a \pmod p$ holds, whether $p$ divides $a$ or not

i don't know where to start. think I'm over thinking it. but here is what I have but can really connect the dot. Let $\{0, 1, 2, \ldots, p - 1\}$ be a complete residue system modulo $p$. We show that ...
1
vote
1answer
44 views

Reducing modulo powers of a prime

If p is an odd prime and a is coprime to p, how would one go about reducing $a^{p^{k-1}}\mod p^k$? Using Euler's formula we can get a value for $a^{p^{k-1}(p-1)}\mod p^k$ but I can't really see how ...
1
vote
1answer
48 views

Why is $\frac{\gcd(c_2,c_3)}{\gcd(c_1,c_2,c_3)}=\gcd\left(\frac{c_2}{\gcd(c_1,c_2)},c_3\right)$

Why is true that $\operatorname{lcm}(\gcd(c_1,c_3),\gcd(c_2,c_3))=\gcd(\operatorname{lcm}(c_1,c_2),c_3)$ ? LHS is $\displaystyle\frac{\gcd(c_1,c_3)\gcd(c_2,c_3)}{\gcd(c_1,c_2,c_3)}$ RHS is ...
2
votes
1answer
56 views

How to find the smallest $n$ such that $n^a\equiv 1 \pmod p$

Given a prime $p$ and number $a$, how do I find the smallest $n$ such that $n^a\equiv 1 \pmod p$? Is there a non trial-and-error method? Edit: obviously removing $n=1$!
0
votes
3answers
37 views

Assume $\gcd(a, m) > 1$. Show that there cannot possibly exist a power $k$ such that $a^k\equiv 1 \bmod m$.

i have no idea where to start to show this. i'm assuming that i should probably use Fermat little theorem and division algorithm. but i don't know where to start.
1
vote
3answers
43 views

How can I prove $(a+b)\mod m = ((a \mod m) + (b \mod m)) \mod m$? [closed]

How Can I prove $$(a+b) \mod m = ((a \mod m) + (b \mod m)) \mod m?$$
0
votes
1answer
179 views

Find a div m and a mod m when

Find a div m and a mod m when $a = -111$, $m = 99$ I can't find the formula anywhere in my book.
4
votes
1answer
74 views

When is $20q^4-40q^3+30q^2-10q$ a square for positive integer $q$?

For what $q$ is the following polynomial a square? $$ \begin{align} &20q^4-40q^3+30q^2-10q\\ =\:&10q(q - 1)(2q^2 - 2q + 1) &q\in\mathbb N \end{align} $$ I know of two single cases, ...
1
vote
2answers
45 views

Prove that if a|b and b|c then a|c using a column proof that has steps in the first column and the reason for the step in the second column.

Let $a$, $b$, and $c$ be integers, where a $\ne$ 0. Then $$ $$ (i) if $a$ | $b$ and $a$ | $c$, then $a$ | ($b+c$) $$ $$ (ii) if $a$ | $b$ and $a$|$bc$ for all integers $c$; $$ $$ (iii) if $a$ |$b$ and ...
0
votes
1answer
21 views

Squaring Polynomial over $\Bbb F_2[X]$ Is Equivalent to Squaring Argument

Thanks to some assistance below, I can now show that if $g(X) \in \Bbb F_2[X]$ then $g(X)^2 = g(X^2)$. Is there some more direct way to prove this special case (not that the original proof is ...
2
votes
1answer
64 views

2014A AMC solution question

From: AMC 10 Q25 Solution I get everything besides the last part. How in the world does he get: $$3k + 2(867 - k) = 2013$$ I don't understand how he got this? What does this mean? Literally ...
0
votes
0answers
25 views

exponent and modulus

Good day all, I am working on a equation and not getting it to work correctly. Hope to seek some advice. $r1 = (m+xr-m1)x^{-1}\pmod q$ $y^{r1} = (y^m)^{x^{-1}} \times y^{xr(x^{-1})} \div ...
1
vote
1answer
55 views

Show that $1^m+2^m+\cdots+(p^2)^m\equiv-p\pmod{p^2}$ when $p-1\nmid m$

Can you please help of how can I approach this proof. I have seen a proof of the power sum of p in the internet but it doesn't seem very helpful. I want to show that $S_m(p^2)$ is congruent to $-p$ ...
0
votes
2answers
75 views

Solve $2^x=13 \bmod 3^4$

Solve $2^x=13\bmod 3^4$ I know $\log13=30\bmod 3^4$ and $\log16=15 \bmod 3^4 $ I've tried subbing $\log13/\log16$ for $2$ but I am not sure what to do next.
1
vote
0answers
36 views

Characterization of two sets

I am interested in the following problem: Let $n \in \mathbb{N} $ . We define the function $S_n: \mathbb{Z_n^*} \to \mathbb{Z_n} $ \begin{align} S_n(\bar a) := \bar 1 + \bar a + \bar a^2 + ...+ ...
2
votes
1answer
44 views

find all integer $x$ such that $7x\equiv 2x$ (mod 8)

I am trying to find all integer $x$ such that $7x\equiv 2x$ (mod 8) First, I have $$ 7x-2x=8k \hspace{0.1in} (\text{where} \hspace{0.1in}k\in\mathbb{z}) $$ $$5x=8k$$ $$x=\frac{8k}{5}$$ Does ...
1
vote
1answer
60 views

Proving something about the sequence of powers of 3 mod 10. Oh boy

Given the sequence $t_0=3, t_1=3^3,...$ so that $t_{n+1}=3^{t_n}$, prove $t_{k+1} \equiv t_k \mod 10^n$ for all integers $n \leq k$ My work so far: I thought it was a pretty obvious case for ...
3
votes
5answers
35 views

Prove that $m$ is an integer

Suppose $n$ is a odd integer. It satisfies: $$3^{s} < n < 3^{s+1}$$ For some integer $s \ge 0.$ Show that: $$m = \frac{n - 3^{s}}{2}$$ Is an integer. So, $$2m = n - 3^{s}$$ But that wont ...