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
34 views

Generalized Fibonacci Sequences with Modular Arithmetic

Consider the following generalized fibonacci sequence: For $m,p$ positive integers and $g_k =g_k (mod m)$, then for $n=1,2,3,...$ $g_{n+p}=g_{n+(p-1)}+g_{n+(p-2)}+...+g_{n+1}+g_n (modm)$ I need to ...
2
votes
2answers
67 views

If $\gcd(a,b)=1$, is $\gcd(a^x-b^x,a^y-b^y)=a^{\gcd(x,y)}-b^{\gcd(x,y)}$?

If $\gcd(a,b)=1$, is it true that $$\gcd(a^x-b^x,a^y-b^y)=a^{\gcd(x,y)}-b^{\gcd(x,y)}\;?$$ I know that $a^{\gcd(x,y)}-b^{\gcd(x,y)}\mid a^x-b^x$ and $a^{\gcd(x,y)}-b^{\gcd(x,y)}|a^y-b^y$, so I ...
1
vote
1answer
102 views

Is there an expression for $x+x^{2}+x^{4}+ \cdots + x^{2^n}$?

Is there an expression for $x+x^{2}+x^{4}+ \cdots + x^{2^n}$ which has finitely many terms or such? I have in mind an expression of this form that I am considering mod $m$ that I wish to compute. ...
1
vote
0answers
16 views

Prove an upper bound for the multiplicative order of a congruence

This is a problem from elementary Number Theory. It's the only one I couldn't figure out and it's bothering me. Definition: Let a and n be natural numbers with (a, n) = 1. The smallest natural number ...
1
vote
2answers
31 views

Modular Arithmetic with Sines

Given $$\sin(10^{100})+\sin(n)=0$$ find $n$. I wrote so far that $$\sin(10^{100})=\sin(10^{100} \mod 360)$$ and I noticed that $10^3 \mod 360=280$ and $10^4 \mod 360=280$ so I (correctly) assumed ...
0
votes
1answer
38 views

Prove that a is a primitive root mod p if and only if -a has order (p-1)/2

Consider a prime p $\in\mathbb{N}$ of the form 4t+3, with t $\in\mathbb{N}$. Prove that a$\in\mathbb{Z}$ is a primitive root mod p if and only if -a has order $\frac{(p-1)}{2}$. I showed most of the ...
1
vote
1answer
48 views

Inverse of matrix mod $26$ wolframalpha wrong

I want to find $A^{-1} \pmod{26}$ for $A=\begin{bmatrix}10&3\\5&3\end{bmatrix}$ and I did the conventional $\frac{1}{ad-bc}\begin{bmatrix}d&-b\\-c&a\end{bmatrix}$ and found the ...
0
votes
1answer
13 views

Possible dividers of a number of three digits

For each natural number n of 3 decimal digits (thus with the first non-zero digit), we consider the number n0 n obtained by eliminating its possible digit equal to zero. For example, if n = 205 then ...
1
vote
0answers
18 views

Help with repeated squaring

I'm having trouble figuring out how to use repeated squaring to figure out 289^377 mod 589. I've seen other websites break the exponent down into (1 + 4 + 16 ... ), but I'm not sure when to do that.
0
votes
1answer
63 views

all elements of ($Z$/p$Z$)* are cubes

Let $p$ be a prime An element $a \in$ ($Z$/p$Z$)* is called a cube if there exists $b \in$ ($Z$/p$Z$)* such that $a = b^3$ How to show that all elements of ($Z$/p$Z$)* are cubes ? And if $p \equiv ...
1
vote
2answers
66 views

Form of a prime dividing a certain difference of two prime powers.

Let $p$ and $q$ be odd primes. If $q|(a^p-1)$ then, either $q|(a-1)$ or $q=(2rp+1)$ for some integer $r$.
0
votes
1answer
50 views

Product of Distinct Primitive roots

Let $p$ be an odd prime. Show that the product of the distinct primitive roots, $\mod{p}$, is $\equiv$ $1$ or $-1$ $\pmod{p}$. I think this can be done by viewing the primitive roots as a elements of ...
0
votes
2answers
31 views

Modulo operations over Gaussian Integers

Given $a,b\in\Bbb Z[i]$, is there a definition and calculation of remainder $a\bmod b$? Could you provide examples say $35\bmod (2+3i)$, $(43+7i) \bmod (22+8i)$?
4
votes
0answers
53 views

Exploiting a crypto backdoor based on a polynomial

At a capture-the-flag competition during the weekend, there was a task that involved the following polynomial over the field $F = \mathbb{F}_P$ of integers modulo $P = 571787215471557516425591$ (yes, ...
1
vote
0answers
53 views

Prime twins and $1 \mod 30$ confusion

Jie Wu improved Brun's theorem and showed that the number of prime twins up to $n$ satisfies for sufficiently large $n$ : $$\pi_2(n) < 4.5 \frac{n}{ln(n)^2} $$ However this confused me while ...
-4
votes
3answers
70 views

$n \equiv 1 \pmod{2m} \Rightarrow n \equiv 1 \pmod{m}$ but converse is false [closed]

Prove if $n \equiv 1 \mod 16$, then $n \equiv 1 \mod 8$ BUT if $n \equiv 1 \mod 8$ then it is not necessarily true that $n \equiv 1 \mod 16$. Prove that if $n \equiv 1 \mod 2m$, then $n \equiv 1 \mod ...
0
votes
0answers
17 views

how to prove a non-negative integer n to be divisible by positive integer d is n mod d = 0

I'm not sure how to prove that, a necessary and sufficient condition for a non-negative integer n to be divisible by a positive integer d is that n mod d = 0. I get that I have to prove the cases of ...
2
votes
2answers
56 views

Modular Congruence with prime factorization!

Show that if n is a natural number and n is congruent to 3 (mod 4) then one of the prime factors of n must also be congruent to 3 (mod 4) I honestly don't know where to begin with this problem. It ...
0
votes
1answer
16 views

Modular Congruence

I need to somehow use mod 2 and Modular congruence to prove whether or not the following number is even or odd: $722^{77}$-$333^{99}$($55^{100}$) What I was thinking about doing was evaluating as two ...
0
votes
2answers
59 views

Suppose that $n \in \mathbb{Z}$. Prove that if $n^2 + 1$ is a perfect square, then $n$ is even.

This is a homework problem that I cannot figure out. I have figured out that if $n^2 + 1$ is a perfect square it can be written as such: $n^2 + 1 = k^2$. and if $n$ is even it can be written as ...
3
votes
2answers
35 views

What is $5^{11\times31}$ congruent to in modulo $11\times 13$?

My attempt: $$ 5^{11\cdot31} ≡5^{341} \pmod {143}$$ Using FLT where $$a^{p-1} ≡ 1 \pmod p$$ I get $$≡(5^{142})(5^{142})5^{57} \pmod {143}$$ $$≡5^{57} \pmod {143}$$ This is where I'm stuck.
11
votes
4answers
1k views

In mod3, is 3 greater than, or less than 1?

In modular arithmetic (say mod3), is the largest number (3) greater than or less than the smallest number? Because, intuitively, it would be greater, but 3+1=1 in mod3 which would suggest that it is ...
0
votes
0answers
57 views

If $N$ divides $a$ and $N$ divides $b$ then

If $N$ divides $a$ and $N$ divides $b$ then $N$ divides $a \cdot b$? Is the statement true? I mean. $$a \equiv 0 \pmod{N}$$ $$b \equiv 0 \pmod{N}$$ $$\implies ab \equiv 0 \pmod{N}$$ But I am ...
4
votes
2answers
53 views

Find All Solutions to System of Congruence

$$ \begin{cases} x\equiv 2 \pmod{3}\\ x\equiv 1 \pmod{4}\\ x\equiv 3 \pmod{5} \end{cases} $$ $ n_1=3\\ n_2=4\\ n_3=5\\ N=n_1 * n_2 * n_3 =60\\ m_1 = 60/3 = 20\\ m_2 = 60/4 = 15\\ m_3 = 60/5 = 12\\ ...
5
votes
2answers
44 views

Simultaneusly solving $2x \equiv 11 \pmod{15}$ and $3x \equiv 6 \pmod 8$

Find the smallest positive integer $x$ that solves the following simultaneously. Note: I haven't been taught the Chinese Remainder Theorem, and have had trouble trying to apply it. $$ \begin{cases} ...
0
votes
0answers
22 views

Are the expressions (a/b) %c and (a%(b*c)) /b equivalent?

As far as I know, to determine (a/b)%c, we need to determine (b^-1)%c which can be done using extended euclid, fermat's theorem, euler's theorem or there may be some other way, but what we must need ...
0
votes
2answers
30 views

Let $a,x \in \mathbb{Z}$ and $n \in \mathbb{N}$. Suppose that $ax ≡ 1 \mod n$. Prove that $a$ is coprime to $n$

Let $a,x \in \mathbb{Z}$ and $n \in \mathbb{N}$. Suppose that $ax ≡ 1 \mod n$. Prove that $a$ is coprime to $n$. I have shown that $1=ax-ny$ for some $y \in \mathbb{Z}$ but I don't know if ...
3
votes
3answers
37 views

Application of the Binomial Theorem-remainder

I am having a confusion in this question- What is the remainder when $7^{103}$ is divided by 24? I attempted it as follows - It can be written as $(7^2)^{51} \cdot 7$ Which can be written as ...
1
vote
1answer
84 views

Question concerning the Dirichlet density of a subset of the set of primes

I have the following question: I am reading Serre's book "A Course in Arithmetic" (see http://www.math.purdue.edu/~lipman/MA598/Serre-Course%20in%20Arithmetic.pdf). On page 75, it is stated that the ...
1
vote
5answers
80 views

No natural numbers satisfy $n\equiv n^2-4\pmod9$

Prove that for all natural numbers, $n$ is not congruent to $n^2-4\pmod9$. I'm trying to prove this by contradiction and say that if they were congruent $\pmod 9$ it could be expressed as $9\mid ...
1
vote
3answers
57 views

Modular Arithmetic with large exponents!

Decide whether each of the following is true or false without using a calculator: The problem is: $$11^{99}\equiv 1\pmod{5}$$ Now I know I can break the $11$ into $(10+1)^{99}$ and maybe rewrite it ...
2
votes
1answer
45 views

mod operation proof

Prove: $ ab\,\bmod\,d = ((a\,\bmod\,d)\,(b\,\bmod\,d))\,\bmod\,d $ where $a$, $b$ and $d$ are non-negative integers. Reference : http://en.wikipedia.org/wiki/Modulo_operation#Equivalencies Context ...
1
vote
1answer
21 views

Am I using the Legendre/Jacobi symbols correctly?

I want to check if $21$ is a square $\mod 25$, so the Jacobi symbol is: ${21 \choose 25}$. $25$ is not a prime, so I can't split up the numerator yet for the Legendre symbol. So I prime factorize the ...
1
vote
2answers
53 views

How to check if $5$ is a square $\mod 701$ without a calculator

The Legendre symbol tells us to calculate $5^{350} \mod 701$, but this question was on an exam where no calculators are allowed, so I wasn't able to do this question. How can you find if $5$ is a ...
0
votes
0answers
35 views

How to determine if $3$ is a square $\mod 97$

The answer is that it is since $10^2 \equiv 3 \mod 97$, but how do we determine that $3$ is in fact a square without having to find explicitly the square that is $3 \mod 97$ ($100$ in this case)?
2
votes
4answers
35 views

Chinese Remainder Theorem for $x\equiv 0 \pmod{y}$

Can anyone solve the following system of congruences using CRT step-wise, without skipping any part? $$\begin{cases} x\equiv 3 \pmod{7}\\ x\equiv 3 \pmod{13}\\ x\equiv 0 \pmod{12}\end{cases}$$ The ...
0
votes
0answers
25 views

How can I verify the result of modular exponentiation

I ask a computer to calculate $x^y \pmod z$, where $x,y,z$ are all large numbers. How can I verify the correctness of the result returned by the computer. I assume that I myself cannot afford ...
0
votes
2answers
28 views

Exponentiation in Modular Arithmetic

I feel like this is a fairly straightforward question, but I've been having a great deal of difficult computing one modular arithmetic expression. It's this: $9 ≡ 3^a \pmod{17}$ How does one go ...
1
vote
3answers
31 views

affine cipher $ax+b \mod m$

I have an affine chipher $ax+b \mod m$ For what values $a,b$ is this an injective encryption function? From what i understand thats the case when $a$ and $m$ are coprime, so $gcd(a,m)=1$ and the ...
5
votes
1answer
71 views

Is there a $k$ such that $2^n$ has $6$ as one of its digits for all $n\ge k$?

It is true that every power of $2$ of the form $2^{6+10x}$, $x\in\mathbb{N}$, has $6$ as one of its digits. Something more is true, the last two digits are either $64$ or $36$. The OP suggests that ...
1
vote
1answer
50 views

Artificial Integer?

Consider a function $$ f: \Bbb{Z} \rightarrow \Bbb{Z} $$ Over the integers. Furthermore consider a number E such that there doesn't exist an integer R such that $f(R) = E$ or formally stated $$ E ...
3
votes
1answer
137 views

Prove this Floor function indentity $\sum_{k=0}^{n-1} \bigl\lfloor \frac{ak+b}{c} \bigr\rfloor$

Assmue $a,b,c$ be postive integers. Show that: $$\sum_{k=0}^{n-1} \left\lfloor \frac{ak+b}{c} \right\rfloor = \sum_{k=0}^{\left\lfloor \dfrac{an+b}{c}\right\rfloor} ...
1
vote
7answers
73 views

Why is $a^{5} \equiv a\pmod 5$ for any positive integer?

Why is $a^{5} \equiv a\pmod 5$ for any positive integer? I feel like it should be obvious, but I just can't see it. Any help appreciated. Edit: without Fermat's theorem.
0
votes
0answers
31 views

Carmichael numbers and primitive roots of unity

Let $n$ be a Carmichael number. Is it possible for an integer ring $\mathbb{Z}_n$ to contain primitive $(n-1)^{th}$ roots of unity? Or do only only primitive roots of unity of degree $\quad k < ...
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
30 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 ...