Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.

learn more… | top users | synonyms

1
vote
5answers
95 views

Solve the following equivalency

$$n^2 \equiv 2 \pmod{9}$$ I don't even know where to begin. Can you provide a step-by-step solution? Some people seem to solve them as if they were regular equations. So, is $n^2 \equiv 2 \pmod{9}$? ...
1
vote
1answer
422 views

question on how to decrypt the message

A message is encrypted using an affine cryptosystem in which plaintext uses the 26 letters A through Z (all blanks are omitted), the letters are identified with the residue classes of integers (mod ...
0
votes
3answers
228 views

find all rational numbers p/q such that $|p/q-17/5|< 1/q^2$

This is a question in my assingment. I needto find all rational numbers p/q such that $|p/q-17/5|< 1/q^2$. Any ideas ? Thanks for any help!
2
votes
3answers
206 views

Legendre symbol problem

This is a part of my HW. Let $p$ be an odd prime and $a$ an integer coprime to $p$. I am asked to show that $$(\frac{a}{p})+(\frac{2a}{p})+\cdots+(\frac{(p-1)a}{p} )= 0.$$ I got no idea to solve it . ...
0
votes
3answers
164 views

Chinese Remainder Theorem Modified

Suppose we have a set of n congruences of form $$ X \equiv a1 \pmod p$$ $$ X \equiv a2 \pmod q$$ $$ X \equiv a3 \pmod r$$ where p, q, r are relatively prime. Let $$P = \Pi \hspace{5pt}p^aq^br^c$$ ...
2
votes
1answer
911 views

Primitive roots modulo a prime number

Suppose $p$ is a prime number. I want to show that if integers $a,b$ are such that $p$ does not divide $b$ and for any $y$ which has the properties (1) $y$ is not divisible by $p$ and not a ...
1
vote
6answers
125 views

Simple linear congruence question

Where did the following argument go wrong? (The correct answer in $\mathbb{Z}_{100} $is just $81$.) Working mod 100: $$21x\equiv1$$ $$105x\equiv5$$ $$5x\equiv5$$ $$x\equiv1,21,41,61,81$$ Thank you.
3
votes
1answer
293 views

Multiplicative Möbius inversion formula.

There is a very simple proof for Möbius inversion formula through convolution: If $A$ is a UFD and $B$ is a ring, $f,g:A\rightarrow B$ two functions, then $$(f\ast g)(n) = \sum_{k\cdot l = ...
0
votes
1answer
124 views

natural number n such that whether or not 11 is a square modulo a prime $p$ only depends on the congruence class of $p$ modulo $n$

Find a natural number n such that whether or not 11 is a square modulo a prime $p$ only depends on the congruence class of $p$ modulo $n$ (apart from finitely many exceptions), and find those ...
3
votes
1answer
159 views

Modifying Euler Totient Function

To calculate the number of integers co-prime to $N$ and less than $N$ we can simply calculate its ETF (Euler's totient function). However to calculate the number of integers co-prime to $N$ but less ...
2
votes
1answer
41 views

Distribution of $\bmod$ on the $+$ operator

We know that $(a*b) \pmod n \equiv (a \pmod n * b \pmod n) \pmod n$. What other distributive attributes of the mod exist? Specifically when we have: $(a + b + c) \pmod n \equiv ?$
0
votes
3answers
118 views

Possibility of having exactly 5 primes in a sequence of $10$ consecutive positive integers.

Does a sequence of positive integers $a_n$ such that the sequence $a_n, \space a_n+1,\space a_n+2,\space \cdots, \space a_n+9$ contains exactly $5$ primes exist? Is such sequence finite or infinite? ...
1
vote
0answers
45 views

Linear expression for the elements belonging to the same modulo order

$\newcommand{\ord}{\operatorname{ord}}$ Let $p$ is any prime and $(a,p)=1$ (i)If $\ord_pa=2,$ We know there can be $\phi(2)=1$ element that belongs to order$=2$. (ii)If $\ord_pa=3,a^3\equiv ...
2
votes
1answer
145 views

Euler product of Dirichlet Series

For $n$ a positive integer, let $f(n)$ be the squarefree part of $n$. Find the Euler product for $\mathfrak D_{f}(s)$ where $\mathfrak D_{f}(s)$ is the Dirichlet Series of $f$.
1
vote
1answer
146 views

Bounding a Von-Mangoldt Summatory Function

Can someone find a function f(n) satisfieing these bounds? Can you also prove that it does? $$ \sum\limits_{k=1}^n \Lambda(k) ...
2
votes
2answers
208 views

Where did I go wrong on computing the legendre symbol $\left(\frac{150}{1009}\right)$

Where did I go wrong on computing the legendre symbol $\left(\frac{150}{1009}\right)$. I know the answer is $1$. For some reason every way I compute this legendre symbol I get $-1$: ...
1
vote
1answer
135 views

Mertens' asymptotic formula for $\prod \left(1-p^{-1}\right)$ without constant

I've heard that there is an easy way to derive the asymptotic $$\prod_{p\le x} \left(1-\frac{1}{p}\right) \sim \frac{c}{\log(x)}$$ if one isn't interested in deriving $c=e^{-\gamma}$. I don't see how ...
2
votes
1answer
157 views

Finding the Probability that a randomly chosen integer is a square or psuedo-square

Definition: $n$ is a psuedo-square if the legendre symbol $(\frac{n}{p}) = 0$ or $= 1$ for $p = 3, 5, 7, 11$. I want to find the probability of $n$ being a square or psuedo-square. I know that any ...
0
votes
2answers
156 views

Number of zeros in decimal expansion

What is the number of zeros in the decimal expansion of $11^{100}-1$?
0
votes
3answers
356 views

Fastest way to solve linear congruent equation

Whats the fastest way of solving $85x=12\pmod{19}$. I can solve it but I want a quick way. I can use facts like $0=\pm19\pmod{19}$ but I am not that fast using that method.
1
vote
2answers
94 views

Prove that if $ac$ has a square root modulo $p$ and if…

Let $p$ be a prime and suppose $\gcd(a,p)=\gcd(c,p)=1$. Prove that if $ac$ has a square root modulo $p$ and if $a$ has a square root modulo $p$ then $c$ has a square root modulo $p$.
2
votes
1answer
158 views

In number theory, is it always true that..

Note: $\text{ord}_ma = k$ here is the smallest $k$ such that $a^k \equiv 1 \pmod m$, not the highest power of $m$ that divides $a$. Is it always that case that if $\text{ord}_ma=k$ and if ...
0
votes
1answer
337 views

Prove that $\operatorname{ord}_m(ab)=kl$

Suppose that for some $m\ge1$ and $a$ and $b$ with $\gcd(a,m)=\gcd(b,m)=1$ we have $\operatorname{ord}_ma=k$ and $\operatorname{ord}_mb=l$ where $\gcd(k,l)=1$. Prove that ...
0
votes
2answers
70 views

finding all $(a,b)$

How to find all $(a,b)$ in $\mathbb{N}$ which $( 2a - 1 , 2b + 1 ) = 1 $ and $ a+b \mid 4ab + 1$
0
votes
1answer
43 views

Supposing $x,y \in \mathbb{Q}^+$, does there exists $n \in \mathbb{Z}^+$ such that $x^n>y$ whenever $x>1$, or $x^n<y$ whenever $0<x<1$?

If $x,y$ are rationals and both positive numbers, how can I show: if $x>1$ there is a positive interger $n$ such that $x^n>y$, if $0 < x < 1$ there is a positive interger $n$ such that ...
2
votes
1answer
150 views

Describe in terms of congruence class all of the odd primes $p = 2m+1$ such that $p \mid 10^m - 1$

Describe in terms of congruence class all of the odd primes $p = 2m+1$ such that $p \mid10^m - 1$. $p=2m+1 \iff 2m \equiv 1 \pmod p$ $p \mid 10^m - 1 \iff 10^m \equiv 1 \pmod p$ So, I have $2m = ...
1
vote
1answer
299 views

The meaning of the Jacobi Symbol and its efficient evaluation

Are the following jacobi symbol evaluations correct?: $(\frac{35}{53}) = -1$ $(\frac{68}{233}) = -1$ $(\frac{126}{509}) = 1$ $(\frac{672}{1297}) = 1$ $(\frac{1235}{3499}) = -1$ Also what is the ...
4
votes
3answers
806 views

Order of elements modulo p

Let $p$ be prime. Suppose that $x\in Z$ has order 6 mod p. Prove that $(1-x)$ has order 6 mod p as well. I know that I need to show that the order can't be 2 or 3 (4 and 5 are trivial cases), but I'm ...
1
vote
0answers
68 views

Number of ways to write a dyadic rational number into a sum of fixed $n$ terms of negative powers of $2$

As the title describes, I will post here my question clearer: Let $z=\frac{m}{2^k}$ be a dyadic rational number in $(0,1)$ where $m$ is odd and $k >0$, and also $n$ is a fixed positive integer. ...
3
votes
2answers
141 views

A lower bound for Waring's Problem for sufficiently large numbers: $G(k) \ge k+1$

I need to show that, if $G(k)$ is the solution to Waring's Problem for $k$ and for sufficiently large $n$, then: $$G(k) \ge k + 1$$ So I need to establish that: $$x_1^k + x_2^k + \dots + x_k^k = n ...
0
votes
1answer
176 views

How many numbers are there which are less than 100 and can be expressed as sum of three of their factors?

I know the answer is 16. I.E all the multiples of 6, but what is the actual concept behind this? I was trying to understand an explanation given by Euler, but in vain. Kindly explain in layman terms. ...
8
votes
1answer
2k views

Is greatest common divisor of two numbers really their smallest linear combination?

In a lecture note from MIT on number theory says: Theorem 5. The greatest common divisor of a and b is equal to the smallest positive linear combination of a and b. For example, the greatest ...
1
vote
1answer
48 views

Radix representation and a congruent relation

Let $\epsilon_p(n)=\lfloor {n/p}\rfloor+ \lfloor {n/p^2}\rfloor+\cdots$ i.e the largest poswer of $p$ (prime) that divides $n!$ where $n$ is an integer. Let $(\alpha_0\ldots\alpha_m)$ be a ...
1
vote
2answers
70 views

Prove that if $a \equiv b \pmod{3}$, then $2a \equiv 2b \pmod{3}$.

A friend and I are completely stumped on this prompt, and are even having trouble seeing how its statement is true. Any help will be appreciated! Prove that if $a \equiv b \pmod{3}$, then $2a \equiv ...
1
vote
1answer
126 views

Bounds for Waring's Problem

The question is posed as such: If G(k) = min{ g : every "sufficiently large" natural number can be written as the sum of g kth powers } Then I seek to prove two things. First, to establish the ...
0
votes
3answers
102 views

Find a number $x<100$ that satisfies three congruences.

Find a number $x<100$ for which all three statements are true: When $x$ is divided by $3$, the remainder is $2$. When $x$ is divided by $4$, the remainder is $3$. When $x$ is divided by $5$, the ...
8
votes
3answers
220 views

$a+b=c \times d$ and $a\times b = c + d$

There is a 'nice' relationship between the integers (1,5) and (2,3) as $$1+5=2 \times 3;$$ $$1\times 5 = 2 + 3.$$ So I tried to find all positive integers pairs $(a, b)$ and $(c, d)$ such that ...
3
votes
1answer
275 views

Bounding the finite sum of $\frac {\log n}{n}$

So I'm completely lost in my class on Additive Number Theory. I've been trying to show that there exists a constant B such that $$\sum_{n \le x}\frac{\log n}{n} = \frac{1}{2}\log ^2x + B + ...
0
votes
1answer
558 views

Using Partial Summation

So here's a problem I've been working on for some time. Define $\gamma$ as $$ \gamma = 1-\int_1^\infty \frac{f(t)}{t^2} dt\,. $$ where $f(t) = t - [t]$ What I'm trying to show (unsuccessfully) is ...
2
votes
1answer
79 views

Intervals of Circle Method

I'm trying to understand how to use the circle method to derive an asymptotic formula for Waring's Problem. Do so using the circle method developed by Hardy and Littlewood. In doing this, I want to ...
3
votes
1answer
69 views

$ x_1 + x_2 + x_3 +\cdots + x_m = k $

What I'm tyring to show is the number of solutions to the equation of natural numbers; $$ x_1 + x_2 + x_3 +\cdots + x_m = k $$ is equal to $$ \binom{m + k - 1} m $$ To be blunt, I have no idea ...
2
votes
1answer
109 views

Show that if $p\ge5$ then $(mp)! \equiv m!p!^{m} \pmod{p^{m+3}}$.

This is a question in Niven's An Introduction to the Theory of Numbers. I believe a result from the previous exercise If $p\geq 5$ and $m$ is a positive integer then $\binom{mp-1}{p-1} \equiv 1 ...
2
votes
2answers
69 views

For what values of the variable x does the following inequality hold:

$\ \frac{4x^2}{\Bigl(1-\sqrt{\ 1\ +2x}\Bigr)^2} < 2x+9$ ... IMO-1960
1
vote
2answers
302 views

Addition or subtraction in GCD and LCM

Suppose that we have two integers $a$ and $b$. Now say that $G = \gcd(a,b)$ and $L = \mathrm{lcm}(a,b)$. Now the value of $G$ and $L$ is given and another integer $c$'s value is given. How can we find ...
4
votes
4answers
167 views

How to eliminate these extra solutions? (finding the gcd of two expressions)

Prove that for any integer $n$, $\gcd (3n^2+5n+7, n^2+1)=1$ or $41$. The following answer is convoluted because I've intentionally created excess solutions. However, I can't figure out how to ...
1
vote
1answer
215 views

Possible primes $p$ $q$ satisfying $a^{3pq}-a \equiv 0 \pmod {3pq}$

For any integer $a$, consider the primes $p$ and $q$ satisfying $a^{3pq}-a \equiv 0 \pmod {3pq}$ Find all such possible $p$ and $q$. So I tried breaking it down into 3 congruences: $a^{3pq}-a ...
0
votes
1answer
71 views

Find the lowest number that's $\geq N$ and that multiplying it with a set of numbers results in natural numbers

Given a set of numbers, I need to find the lowest number that multiplying it with each of the numbers in the set results in a natural number, while being bigger or equal to $N$. For example, for the ...
1
vote
0answers
139 views

Find the lowest common divisor greater than N?

For a given set of numbers, I need to find the lowest common divisor that's higher than a given number, N. Is there a way to do that?
1
vote
0answers
51 views

Algorithms for Performing Large Integer Matrix Operations w/ Numerical Stability

I'm looking for a library that performs matrix operations on large sparse matrices w/o sacrificing numerical stability. Matrices will be 1000+ by 1000+ and values of the matrix will be between 0 and ...
0
votes
2answers
161 views

Find the congruence of $4^{578} \pmod 7$

Find the congruence of $4^{578} \pmod 7$. Can anyone calculate the congruence without using computer? Thank you!