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

learn more… | top users | synonyms (1)

2
votes
0answers
35 views

Where can I find proof - There're infinitely many primes $p$ such that $p(mod\ N)\not\in H$ - Name?

Origin - http://math.uga.edu/~pete/4400FULL.pdf - on p120, Theorem 122 Fix a positive integer $N>2$, and let $H$ be a proper subgroup of $U(N)=(Z/NZ)^{\times}$. There are infinitely many ...
2
votes
2answers
49 views

Multiples of 'k' less than 'n'

How many positive integer multiples of a rational number k exist, that are less than a rational number n?
2
votes
1answer
75 views

Does a solution exist where $p,q$ are odd primes and $p^a - q^b = p^c - q^d$ where $a > c > 1$ and $b > d > 1$

From my thinking so far, there is no solution. Is this an open question or is the answer well known? Here's my reasoning about this issue: If a solution exists, then: $$p^c(p^{a-c} - 1) = ...
2
votes
0answers
101 views

How to prove $\pi ^{3}$ is not constructible from the fact that $\pi $ is not constructible?

I know how to do this for $\sqrt[3]{\pi }$: First suppose it is constructible and then you just set it equal to $x_{0}=\sqrt[3]{\pi }$ and take the third power of both sides. Then you get ...
2
votes
0answers
65 views

Prove that the number of solutions of $a.x^m + b.y^n = c \mod p$ same as $ax^{m'} + by^{n'} =c \mod p$.

This is a question found in Ireland and Rosen's "A classical Introduction to Modern Number Theory", Ch4 Q22. The question was as follows. Q. Prove that the number of solutions (x,y) to the ...
2
votes
0answers
64 views

My first proof employing strong induction / complete induction (very simple number theory). Please mark/grade. [duplicate]

What do you think about my first proof employing strong induction? What mark/grade would you give me? Theorem Every natural number greater than 1 is a product of one or more primes. Proof First, ...
2
votes
0answers
299 views

The set of all natural numbers is closed under addition

I'm trying to prove the theorem described in the title, but my proof is so obvious I doubt it is sufficient. Here's my way of proving it: Definition of addition: Let a, b, and c be natural numbers. ...
2
votes
1answer
540 views

Find an inverse of $a$ modulo $m$ for each of these pairs of relatively prime integers

How would I find the inverse of a given number $a$ modulo $m$, given that $\gcd(a,m)=1$? a) $a = 2$, $m = 17$ $17 = 2 \cdot 8 + 1$ $2 = 1 \cdot 2 + 0$ $1 = 17 - 8 \cdot 2$ <-How do I know ...
2
votes
0answers
30 views

Is there a “simple” answer for this system of equations in *different* natural numbers $R,S,T$?

I have the following system of equations $$ \begin{array} {} 4ST&+&0R&+&1S&+&1T&=&aR \\ 4TR&+&1R&+&0S&+&1T&=&bS \\ ...
2
votes
0answers
48 views

Reference for Hilbert numbers

I've been studying a little bit of number theory, and during such studies I came across this interesting reference to Hilbert numbers, that is, numbers of the form $4n +1$. My question is a purely ...
2
votes
2answers
98 views

How can I show that $a^n|b^n \Rightarrow a|b$

How can I show the following $$a^n|b^n \Rightarrow a|b$$ $$a^n|b^n \Rightarrow b^n=m \cdot a^n \Rightarrow b^n=(m\cdot a^{n-1}) \cdot a\qquad(1)$$ How can I continue? Do I maybe have to suppose ...
2
votes
1answer
90 views

Amicable pair sums - intriguing sexagesimal relationships

Some amicable pair sums show intriguing relationships, for example: 1) The sums of the two numbers in each of the first five pairs have a gcd of 126. 12600 is the sum of those in the fifth pair, ...
2
votes
1answer
41 views

Proving that $\pi(n)=\sum\limits_{j=2}^{n}[\frac{(j-1)!+1}{j}-[\frac{(j-1)!}{j}]]$ when $n$ is an integer

This is a problem out of Rosen's number theory book Show that if $n$ is an integer then $$\pi(n)=\sum\limits_{j=2}^{n}\left[\frac{(j-1)!+1}{j}-\left[\frac{(j-1)!}{j}\right]\right].$$ For $n \neq 4$ ...
2
votes
0answers
52 views

Partitions and divisor functions: what is known about their relations?

If $i\geq 1$ is an integer, we have the following integer valued functions (for any integer $n\geq 0$): \begin{align} p_i(n)&=\textrm{the number of }i\textrm{-dimensional partitions of ...
2
votes
0answers
54 views

arithmetic progression by Dirichlet

The arithmetic progression $a_N=(p-1)N+1$ contains infinitely many primes $q$ by Dirichlet. I have searched this part in wiki, but I din't get any relevant proof. Can any one prove it how $a_N$ ...
2
votes
0answers
77 views

$\frac{ra}{p} + \frac{rb}{p} + \frac{rc}{p} + \frac{rd}{p} = 2 $, with $p$ prime

Let $p>2$ be a prime and let $a$, $b$, $c$, $d$ be integers not divisible by $p$, such that $\{\frac{ra}{p}\} + \{\frac{rb}{p}\} + \{\frac{rc}{p}\} + \{\frac{rd}{p}\} = 2 $ for any integer $r$ not ...
2
votes
0answers
61 views

A question about quadratic residues

Find positive integers $(a,b,c)$ such that $n$ is a quadratic residue modulo some prime $p$ implies $an^2+bn+c$ is also a quadratic residue modulo $p$. What I did: I put $n=m^2$.Then we see $n$ is a ...
2
votes
0answers
63 views

What is the least integer of additive dimension 4?

Say that $m$ is the additive dimension of $n\in\Bbb N$, and write $m=\operatorname{ad}n$, if $m$ is the greatest integer for which there is an irredundant $m$-element set $M\subset\Bbb N$ that ...
2
votes
0answers
56 views

The necessary and sufficient conditions for surrounding sets of numbers

I have a problem that I ran into while exploring the distribution of coprimes of a number $n$. Consider two sequences of natural numbers $R$ and $S$. We'll say $S \ surrounds \ R$ if $ \ \forall r ...
2
votes
2answers
149 views

99 Ninja missions and a single lantern

From http://blog.liveramp.com/2014/01/30/the-case-of-ninety-nine-ninja/: A team of 99 ninja are each sent out on individual missions by their master. Their master tells the ninja that one of them ...
2
votes
1answer
79 views

The factors of $5^n-3^n-2^n$

I have been assigned the following question. Let $f(n):= 5^n-3^n-2^n$. Prove that (a) $p$ divides $f(p)$ for each prime $p$; (b) $p^{k+1}$ divides $f(n)$ for $n=p^k$, with $p=2,3,5$ and ...
2
votes
0answers
83 views

What is the line of thinking to get $[(n^2+3n+1)^2-5n(n+1)^2]$ from $(n^4+n^3+n^2+n+1)$?

There is this one little tiny step along the working that I don't quite understand, but I think it is better if I write the whole problem and solution for clarity. Problem: Factorise $5^{1995}-1$ ...
2
votes
0answers
52 views

Distribution of Omega values modulo m

Define $\Omega(2^{a_1}3^{a_2}...p_k^{a_k})=a_1+...+a_k$ . I am interested in the density of the values of Omega mod m. If we define the set $S=(x:\Omega(x)\equiv k \text{ mod m})$, I would like to ...
2
votes
1answer
480 views

Positive integers which cannot be expressed as a difference of squares.

This question comes from Saylor course MA111 which took the question from the 2011 Mathcounts national competition. How many positive integers less than $2011$ cannot be expressed as the difference ...
2
votes
1answer
56 views

An Euler problem: How many of these numbers are of the form $a^b$?

How much numbers can be written in the form $a^b$, where $a$ and $b$ are integers that are between $2$ and $100$? How can I start this problem? Any hints please? Thanks!
2
votes
0answers
65 views

yes, why does a negative times a negative make a positive? [duplicate]

for a while I have been interested in the details of the construction of the integers from the natural numbers. credit to the software, for as soon as I began writing this, for it drew my attention ...
2
votes
0answers
69 views

Number Theory Problem relating to binomial coefficient

I want to find greatest common divisor of the binomial coefficients $C(n,1)$, $C(n,3)$, $\cdots$, $C(n,2k+1)$, where $2k+1<n$. Thanks.
2
votes
0answers
51 views

Multiplicative Order Modulo Evaluated Cyclotomic Polynomials

If $\Phi_n(x)$ is the $n$th cyclotomic polynomial, then for which positive integers $n$ and $a>1$ is it true that $\operatorname{ord}_{\Phi_n(a)}(a) = n;$ that is, when is $n$ the smallest positive ...
2
votes
1answer
81 views

Trying to understand an assumption in the proof of Mann's Theorem

I am trying to follow the reasoning in the proof of Mann's Theorem: $$d(C) \ge \min(d(A)+d(B),1)$$ I am clear that we can assume that: $d(A) + d(B) \le 1$ We only need to prove that for every $n \ge ...
2
votes
1answer
47 views

Let $a_n=2^{2n}\left(2^{2n+1}-1 \right)$. Show induction of $n$

Let $a_n=2^{2n}\left(2^{2n+1}-1 \right)$. Show induction of $n$ $$a_{2n+1}=256a_{2n-1}+60\left(16^n\right)$$ $$a_{2n+2}=256a_{2n}+240\left(16^n\right)$$ I tried $n=1$, ...
2
votes
0answers
269 views

Having trouble using the Chinese Remainder Theorem to solve a system of congruences

I'm working on a difficult assignment involving cryptography, and am nearing the end (or so I think). Summed up, I need to solve a system of congruences using the Chinese Remainder theorem. Due to ...
2
votes
1answer
43 views

Question about the properties of Shnirelman density

In elementary methods in analytic number theory by Gelfond and Linnik, the claim is made that if $d(A) + d(B) > 1$, then we can find $A',B'$ where $A' \subseteq A$ and $B' \subseteq B$ such that ...
2
votes
0answers
47 views

${1\over 2}\cdot{3\over 4}\dotsm{2n-1\over 2n}<{1\over \sqrt{3n+1}}$ [duplicate]

I need to show my Induction ${1\over 2}\cdot{3\over 4}\dotsm{2n-1\over 2n}<{1\over \sqrt{3n+1}}$ $P(2)={1\over 2}{3\over 4}<{1\over\sqrt{7}}$, Which is true, $p(k)<{1\over \sqrt{3k+1}}$ ...
2
votes
0answers
48 views

A four-digit square is of the form $aabb$. What's $a^2+b^2$? [duplicate]

The 5772 Ulpaniada included the following question: Consider a four digit square number (a number which is the square of a whole number).Its digit notation is $aabb$ (the thousands digit is $a$, ...
2
votes
0answers
66 views

Smart way to prove this useful inequality?

I want to show the following elementary inequality: $$((|a|+|b|)^p + (|c|+|d|)^p)^{\frac{1}{p}} \le (|a|^p+|c|^p)^{\frac{1}{p}} + (|b|^p+|d|^p)^{\frac{1}{p}}$$ and we have $p \ge 1$. Does anybody ...
2
votes
0answers
53 views

Improving a diophantine approximation

Let $x\in \mathbb T^d=\mathbb R^d/\mathbb Z^d$ and $p/q\in\mathbb Q^d/\mathbb Z^d$ be such that $\|x-p/q\| \leqslant t$ (with $t$ small) and $q\leqslant Q$ can I say that for all $m\in\mathbb N^\star$ ...
2
votes
0answers
33 views

Any primitive root modulo $p^m$ is also a primitive root modulo $p$ [duplicate]

This is the last of the stream of number theory problems I have been looking at that I would like to discuss. Let $p$ be an odd prime number and let $m$ be a positive integer. Prove that any ...
2
votes
1answer
158 views

Find the prime factor decomposition of $100!$ and determine how many zeros terminates the representation of that number.

Find the prime factor decomposition of $100!$ and determine how many zeros terminates the representation of that number. Actually, I know a way to solve this, but even if it is very large and ...
2
votes
0answers
74 views

Using Graphs Changes the Solutions for Diophantine Equation? Imperfection of Graph?

Solve the Diophantine equation $$x^2+4y^2=z^2$$ The problem here is that I derived solutions using two different methods, and the both solutions do satisfy the given equation yet they are ...
2
votes
0answers
92 views

Need to find a better algorithm to solve a project euler problem dealing with coprime pairs.

I've been working on this for a while and found several solutions so far, but none are fast enough to find the necessary $S(10^7)$. Here is the question: For an integer $M$, we define $R(M)$ as ...
2
votes
0answers
90 views

Sums of powers.

Here's the problem: Show that $19^{19}$ is not the sum of a fourth power and a positive or negative cube. I'm just not really sure how to start approaching this problem. Does anybody have any ...
2
votes
0answers
96 views

fourth powers as sums of squares

Is it possible to have a fourth power that is the sum of two squares in four different ways, e.g., $w^4 = a^2 + b^2 = c^2 + d^2 = e^2 + f^2 = g^2 + h^2$ with the added restriction that $e = a+c$ and ...
2
votes
3answers
110 views

The Diophantine equation $x^2 - 97 - 40 = 0$

I am trying to determine whether the equation below has a solution or not $$x^2-97y-40 =0.$$ If a solution exists, $x^2-40$ must be congruent to 0 modulo $97$. If I could show the congruence above ...
2
votes
0answers
181 views

representing integers as linear combination of integers

Let $a,b,a',b'$ be $r-\epsilon_1$ bit positive integers. Let $c,d$ be $s+\epsilon_2$ bit positive integers. Fix a pair $c,d$ and vary $a,b$ over all $r-\epsilon_1$ bit numbers. Do we have almost ...
2
votes
2answers
80 views

show that the even numbers 2k+2,2k+4,…,4k,4k+2 are congruent mod m to…

(first post, hello!) I'm having a bit of trouble with the following problem: let k be a positive integer and let $m = 4k + 3$ show that the even numbers $2k+2, 2k+4,..., 4k, 4k+2 $ are ...
2
votes
0answers
35 views

Is it true that $\sum _{i=0}^a (q-1)^i\binom {n}{i} \leq q^{H_q(a/n)n}$?

Given $q \in \mathbb N$, $q\geq 2$ is it true that \begin{equation*} \sum _{i=0}^a (q-1)^i\binom {n}{i} \leq q^{H_q(a/n)n}? \end{equation*} Here $H_q(x) = x\log _q(1/x) + (1-x)\log _q(1/(1-x))$ is the ...
2
votes
0answers
233 views

The probability that two natural numbers are coprime

What is the probability that two distinct natural numbers are coprime? It has already been shown here and elsewhere that the probability of two random integers $a,b\in\mathbb{N}$, being coprime is ...
2
votes
0answers
110 views

When is a number like “ddd…ddd”+1 (where d is a digit) a perfect square or a prime?

Inspired by Is the number $333, 333, 333, 333, 333, 333, 333, 333, 334$ a perfect square?, I wonder when numbers like these are perfect squares. Certainly, all numbers of the form $000...0001$ are ...
2
votes
1answer
76 views

For any given $n$, there are either infinitely many primitive Pythagorean triangles with one side $n$ units shorter than the hypotenuse, or none

Let $n$ be a positive integer. Prove that if there is at least one primitive Pythagorean triangle where one side is $n$ units less than the hypotenuse, then there are infinitely many. I thought of ...
2
votes
1answer
218 views

A condition for an odd prime to be represented by a binary quadratic form of a given discriminant

Let $f = ax^2 + bxy + cy^2$ be an integral binary quadratic form. We say $D = b^2 - 4ac$ is the discriminant of $f$. If $D < 0$ and $a > 0$, we say $f$ is positive definite. It is easy to see ...