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
2answers
77 views

Find 11^644 mod 645 [duplicate]

Can someone just explain to me the basic process of what is going on here? I understand everything until we start adding 1's then after that it all goes to hell. I just need some guidance. The Problem ...
2
votes
4answers
72 views

Prove if $7\mid a^2+b^2 \longrightarrow 7\mid a$ and $ 7\mid b$

Prove if $7\mid a^2+b^2 \longrightarrow 7\mid a$ and $7\mid b$ What I did: I found the possible remainders for $a^2$ are $0, 1, 2$ and $4$. I think I should say $r_7(a^2)+r_7(b^2)$ can't equal any ...
1
vote
2answers
25 views

Polynomial long division with mod. Trouble with fractions.

For example $4x^4 + x + 1$ divided by $3x + 1$ is $\frac{4x^3}{3} - \frac{4x^2}{9} + \frac{4x}{27} + \frac{23}{81}$ remainder $\frac{58}{81}$. Now I want to do the same division mod $9$, but I can't ...
1
vote
1answer
30 views

Repeating a Sequence

Initially I have provided x and y and the value of x and y repeatedly calculated until at some point the sequence is start repeating. ...
2
votes
2answers
57 views

Integer solutions of $ y^{2} = 5x^{2} + 17 $

Show that there are no integer solutions to the equation $$y^{2} = 5x^{2} + 17$$ using your knowledge of modular arithmetic and congruence classes. My attempt: Take 17 congruence mod 5 and show that ...
3
votes
2answers
89 views

Find three integers $x$ so that $271x \equiv 272\pmod{2015}$

I know that $\forall{a,n}\in\mathbb{Z}:\Bigl[\gcd(a,n)=1\Bigr]\implies\Bigl[\exists{k}\in\mathbb{Z}:ak\equiv1\pmod{n}\Bigr]$ In other words, for every pair of co-prime integers $a$ and $n$, there is ...
1
vote
1answer
23 views

Legendre Symbol $\left(\frac4p\right)$ is always congruent to $1$?

Let$\newcommand\leg[2]{\left(\frac{#1}{#2}\right)}$ $\leg ap$ denote the Legendre symbol. In all cases $a=4$. and $p$ takes values of different odd prime numbers $p$. For $p=5$: $\leg 45$ -> ...
0
votes
1answer
35 views

Generalized Fibonacci Sequence with Modular Arithmetic

Consider the following generalized Fibonacci sequence: Given $a$ and $b$ positive integers, and the known values $g_1, g_2, ...g_b$ where $g_k = g_k$ (mod $a$), then for ...
0
votes
0answers
28 views

Generalized Fibonacci Sequences G_{n+p}

I have been given the following generalized fibonacci sequences: For some positive integer $m,p$, $g_{n+p}=g_{n+p-1}+g_{n+p-2}+...+g_{n+1}+g_n (mod m)$ I have been given two problems: (1) For $m=2$ ...
-1
votes
0answers
40 views

Number of times the while loop is executed

Initially I have provided x and y and the value of x and ...
0
votes
1answer
19 views

Unranking pseudo-random values to produce uniform distribution over all permutations

Following this question (and answers) on SO. The problem is to find a method to produce an unranking of combinatorial objects in random order, but in such a way that all possible orderings are ...
2
votes
2answers
38 views

Simple question about modular arithmetic

I am trying to understand if I could know something about the following relationship: If I have: $b \equiv n \mod a$ $d \equiv n \mod b$ $n \gt 0$ Is it possible to know something ...
0
votes
0answers
7 views

Finding quintuple of numbers with constrained size remainders

Given $A,B\in\Bbb Z_+$ of $(\frac{1}4+\epsilon)\log T$ bits, how could we find three numbers $P,Q,R\in\Bbb Z_+$ of atleast $\log_23 + \frac{1}4\log T$ bits such that in $$A = a_pP + m_p,\quad A = a_qQ ...
1
vote
0answers
28 views

What is the best known lower bound for: $\max_{2\leq i\leq p-1}(ord_n(i)) $?

Given an in integer $n$, and let $p$ be its smallest prime divisor (you can assume that $p$ is very large ). Let $ord_n(i)$ denotes the order of $i$ as an element of $\Bbb Z_n^*$ the multiplicative ...
0
votes
0answers
15 views

Sorting algorithm based on the distance to the factors of the elements of the set

I am trying to understand better the basic concepts of modular-arithmetic and I was playing with a set of integers and decided to order them by using congruences, so I tried to define an algorithm to ...
1
vote
1answer
56 views

Trigonometric Functions And Modular Arithmetic

I was playing around on Wolfram Alpha and plugging in functions such as $$f(x)=2^{x}\bmod{x}$$ to see what some simple graphs might look like. Wolfram also returned some very interesting things such ...
1
vote
1answer
35 views

There exist arbitrarily long sequences of consecutive integers that are not square-free

Let $a$ and $n$ be positive integers. A sequence of $n$ consecutive integers $(a, a+1, a+2,...,a+(n-1))$ is called a Wolczuk of length $n$ if every integer in the sequence is divisible by some perfect ...
6
votes
1answer
100 views

The totient of Fibonacci numbers is divisible by $4$

Let $\{f_i\}_{i\in\mathbb N}$ be the sequence of Fibonacci numbers, i.e. $1,2,3,5,8,13,21,34,55,\cdots$, For every integer $n\gt3$ prove that $$4\mid\phi(f_n)$$ where $\phi$ is Euler's totient ...
4
votes
5answers
194 views

What is $2^{7!}\bmod{2987}$

Find the remainder when $2^{7!}$ is divided by $2987$. I tried to factorise $2987$ to make it simple but it was in vain.
0
votes
1answer
32 views

Calculate $\binom{n}{k}\pmod{10^6+3}$

I want to calculate the value of the following: $$\binom{n}{k}\pmod{10^6+3}$$ $10^6+3$ is prime if it may help. What is the math behind this? I can only understand basic modular arithmetic.
1
vote
1answer
30 views

Can modulo(remainder) be distribute over division?

Let $a\%b$ be the modulo operation, returning the remainder of $a$ when divided by $b$. Is it true that: $$\left(\frac{a}{b}\right)\% 5 = \frac{(a\% 5)}{(b\% 5)}$$ For instance, for $a=10$ and $b=2$ ...
1
vote
1answer
31 views

Is there any modular arithmetic property relating $\mod mn$ to $\mod m$?

We know that addition, subtraction and multiplication can be defined for integer modular arithmetic: for $a \equiv b \mod n$ and $c \equiv d \mod n$, $a+c \equiv b+d \mod n$ and so on. But is there ...
6
votes
1answer
65 views

Let $n$ be a positive integer. Show that the smallest integer greater than $(\sqrt{3} + 1)^{2n}$ is divisible by $2^{n+1}.$ [duplicate]

Let $n$ be a positive integer. Show that the smallest integer greater than $(\sqrt{3} + 1)^{2n}$ is divisible by $2^{n+1}.$ We know that $(\sqrt 3-1)^{2n}<1$
-1
votes
1answer
42 views

Cartesian Point Shifting Period [closed]

Say (x, y) is a point made of nonnegative integers. p and q are two prime numbers and n is another positive integer, with p, q, and n fixed throughout this problem. The point is shifted z number of ...
-5
votes
1answer
66 views

Efficiently calculating sum of series [closed]

The series is: $$\frac n {1!} + \frac {n(n+1)} {2!} + \frac {n(n+1)(n+2)} {3!} + \dots + \frac {n(n+1)(n+2) \dots (n+k-1)} {k!}$$ Where $n$ and $k$ are large. Also if it matters, I only need the ...
0
votes
1answer
39 views

Can this congruence be reduced?

If I have $$(x+1)^2 \equiv 0 \bmod (y+1)$$ Is this as simple as it gets? I have values for $x$ and wish to solve for valid $y$.
0
votes
5answers
89 views

Find $3^{2015} + 7^{2015}\bmod50$

Find the remainder when $3^{2015} + 7^{2015}$ is divided by $50$. I've thought about modular arithmetic, but I'm not sure how to exactly use it here.
0
votes
1answer
36 views

How to compute $(a+1)^b\pmod{n}$ using $a^b\pmod{n}$?

As we know, we can compute $a^b \pmod{n}$ efficiently using Right-to-left binary method Modular exponentiation. Assume b is a prime number . Can we compute directly $(a+1)^b\pmod{n}$ using ...
2
votes
1answer
61 views

Remainder of a power tower under modulo $2013$

I have an expression like this: $$\left(\large 6000^{5999^{5998^{5997^{{\ldots^{1}}}}}}\right)\bmod 2013$$ Then which method should I use to solve it? Please provide the method not the answer. ...
0
votes
1answer
33 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
15 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 ...
0
votes
3answers
27 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
35 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
46 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
62 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
votes
2answers
63 views

If p is an odd prime then prime divisors of $(2^p-1)$ [duplicate]

If $p$ is an odd prime Prove that the prime divisors of $(2^p-1)$ are of the form $(2rp+1)$.
1
vote
2answers
65 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
49 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
30 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
52 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
69 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
16 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
53 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
15 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 ...