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

learn more… | top users | synonyms (1)

10
votes
2answers
128 views

Let $a_k=\frac1{\binom{n}k}$, $b_k=2^{k-n}$. Compute $\sum_{k=1}^n\frac{a_k-b_k}k$

Let $a_k=\frac1{\binom{n}k}$, $b_k=2^{k-n}$. Compute $$\sum_{k=1}^n\frac{a_k-b_k}k$$ By computing some partial sums, the answers are 0. It seems an inductive argument is possible.
2
votes
1answer
29 views

Reasoning about Schnirelmann Density: Proving that $d(C) \ge d(A) + d(B)$

I am taking this argument from Gelfond & Linnik's Elementary Methods in the Analytic Theory of Numbers. They state if for every $n \ge 1$, there exists $m \in [1,n]$ where $C(n) - C(n-m) \ge ...
0
votes
3answers
45 views

If s=∅ , T≠∅ then SxT = ∅ . Why? [duplicate]

I recently studied about Cartesian products and I thought that I understood its concept, Until I ran into this expression: If $S=\emptyset$, $\ne\emptyset$, then $S\times T = \emptyset$ . Is an ...
1
vote
1answer
60 views

Finite Continued Fraction Proof

Let $\alpha = \left[a_0, a_1, a_2,\cdots,a_n\right]$ be a finite continued fraction with $a_0 > 0$ and let $C_i = p_i/q_i$ be the convergent of $\alpha$. If $i\ge 1$, prove that ...
1
vote
0answers
47 views

Is it correct? $\lim_{n\rightarrow \infty} \frac{c^{n}}{n!^{\frac{1}{k}}}$

This is what we have $$\lim_{n\rightarrow\infty} \frac{c^{n}}{n!^{\frac{1}{k}}},$$ $$n \in N, k>0, c>0$$ If n->inf ...
1
vote
1answer
62 views

If $gcd(m,n)=1$, prove that $u_{n}u_{m}$ divides $u_{mn}$ for all $m,n \geq 1$.

If $gcd(m,n)=1$, prove that $u_{n}u_{m}$ divides $u_{mn}$ for all $m,n \geq 1$. $u_{1}=u_{2}=1$, $u_{n}=u_{n-1}+u_{n-2}$ for $n \geq 3$
1
vote
0answers
60 views

Find all rational solutions to $x^3 - y^2 = 2$. [duplicate]

Find all rational solutions to $x^3 - y^2 = 2$. The only integers solutions are $(3,\pm5)$: http://mathforum.org/library/drmath/view/51569.html
1
vote
1answer
67 views

If n > 3 and (n + 1) is a square, is there any n that is a prime?

I am looking at properties of squares and came about this property. I am investigating the difference of squares in relation to primes.
0
votes
4answers
73 views

$d\mid n\Longrightarrow d\leq\sqrt n$

$d\mid n\Longrightarrow d\leq n$ Ok, but need to go further, I can say (if yes, how to demonstrate) that $$d\mid n\Longrightarrow d\leq\sqrt n$$
1
vote
1answer
40 views

Number of quadratic residues

I wouId like to prove that for an odd prime power $p^k$, there are $\frac{\phi(p^k)}{2}$ quadratic residues. What I have done is that if $u_1$ is a unit, so is $-u_1$, which means it is somewhere in ...
1
vote
2answers
61 views

$x^2=37\pmod {77}$ is there solution for $x$?

Is there solution for $x$? $$x^2=37\pmod {77}$$ Which method should we use, Diophant equations or? I found nothing by using induction. thanks
-1
votes
5answers
159 views

Solve for $m\in\mathbb{N}$ the equation $\phi (m)=12$

Solve for $m\in\mathbb{N}$ the equation $\phi (m)=12$ I found (by trial) $m=\{13,21,26,28,36\}$, but do not know if misinterpreted the problem, but actually I suppose I have to find an equation ...
1
vote
2answers
38 views

Why this map preserves order?

How to prove that $f:N→\{1,1+1,1+1+1,...\}$ where 1 is an identity element of ordered field, is order-preserving? I guess that maybe property if $a < b$ then $a + c < b + c$ can be useful, but ...
1
vote
1answer
129 views

For what values of m does the equation 35530x + 355y = m have integer solutions?

For what values of $m$ does the equation $35530x + 355y = m$ have integer solutions? (only find the $m$'s for which solutions exist)
2
votes
1answer
61 views

(i).Prove that $\pi_m(n)=\pi_m(n-m)+\pi_{m-1}(n)$ without using the generating functions for $\pi_m(n)$.

Questions: $\pi_m(n)$ is defined as the number of partitions of n in which each part is no larger than m. (i).Prove that $\pi_m(n)=\pi_m(n-m)+\pi_{m-1}(n)$ without using the generating functions for ...
9
votes
2answers
124 views

if such$\sqrt{37}+\sqrt{47}<\dfrac{n}{m}<\sqrt{41}+\sqrt{43}$ Find this $m$ minimum

let $m,n\in N^{+}$, if such $$\sqrt{37}+\sqrt{47}<\dfrac{n}{m}<\sqrt{41}+\sqrt{43}$$ Find the $m$ minimum the value My try: since $$(\sqrt{37}+\sqrt{47})m<n<(\sqrt{43}+\sqrt{41})m$$ ...
0
votes
1answer
151 views

Prove or disprove the following proposition

Prove or disprove the following proposition: There are no positive integers $x$ and $y$ such that $$x^2 - 3xy + 2y^2 = 10$$
9
votes
1answer
212 views

A congruence in the number of certain ternary strings

Let $a_n$ be the number of ternary strings of length $n$ which do not contain three consecutive symbols that are all different. That is, $$a_n = \Bigl|\bigl\{\,(b_k)_{1\leq k\leq n}\in ...
1
vote
3answers
2k views

Square number that is the sum of two squares in two different ways.

I would like to know if a square number exists that can be expressed as the sum of two other square numbers in more than one different way. Also only natural numbers and excluding zero.
3
votes
3answers
81 views

Prove that for all $n\in\mathbb{N}$, $\frac{s(n)}{d(n)}\geq \sqrt n$

Prove that for all $n\in\mathbb{N}$ $$\frac{s(n)}{d(n)}\geq \sqrt n$$ where $s(n) = \sum_{d|n} d$ and $d(n) = \sum_{d|n} 1$. Being honest, study some time arithmetic functions, and can not ...
0
votes
6answers
157 views

Proof: $\;n^2\;$ is even if and only if $\;n\;$ is even.

Please help how would you go about doing this? I'm studying for a final. This is on a study guide. I'm having a lot of trouble with this class. Prove that $n^2$ is even if and only if $n$ is even. ...
1
vote
3answers
306 views

The gcd of $p+q$ and $p-q$ where $p4 and $q$ are distinct odd primes

Suppose $p$ and $q$ are distinct odd primes. Prove that $\gcd(p+q, p-q) = 2$. I had figured out that $d$ divides $2p$ and $d$ divides $2q$, but I did not recognize to use coprimeness and ...
4
votes
2answers
106 views

Show that $p!$ and $(p - 1)! - 1$ are relatively prime

If $p$ is prime number, with $p>3$ Show that $p!$ and $(p - 1)! - 1$ are relatively prime. I tried $\text{gcd}\;(p!,(p-1)!-1)=d\Longrightarrow d\mid p!$ e $d\mid(p-1)!-1$ having ...
2
votes
1answer
99 views

the sequence 1,11,111,.. and primes

Consider the sequence $\{A_n\} = 1,\, 11,\, 111,\, 1111,\, \dots\,$, where $$A_n = \displaystyle\sum\limits_{k=0}^{n} 10^k$$ I wonder if there exists an $z \in \mathbb{Z}$, such that for all ...
1
vote
1answer
53 views

Pigeonhole question - divisibility by chosen number

This question should be solved with pigeonhole principle. Let $a,n \in \mathbb N$ such that $a$ is a number whose digits are only $3$'s and $0$'s, and $n$ is an unspecified natural number. Show that ...
1
vote
2answers
418 views

Prove that if g is a primitive root modulo p (p is an odd prime), then g belongs to h modulo $p^m$, where $h=(p-1)p^r$ for some r.

Prove that if g is a primitive root modulo p (p is an odd prime), then g belongs to h modulo $p^m$, where $h=(p-1)p^r$ for some r. I know if $g^k \equiv a\pmod{p}$, then $g^k \equiv a\pmod{p^m}$, but ...
3
votes
2answers
233 views

Proving $p\nmid \dbinom{p^rm}{p^r}$ where $p\nmid m$

A question from Advanced Modern Algebra by Joseph J.Rotman. Let $n=(p^r)m $ such that the prime $p\nmid m$.Prove that $p\nmid \dbinom{n}{p^r}$.HINT: Assume otherwise,cross multiply and apply ...
0
votes
1answer
68 views

large numbers - my horse in name the biggest number contest

I read Scott Aaronson's essay Who can name the biggest number and I wonder about a following large number. Take a hundred and apply a factorial function take the result and apply a factorial function ...
3
votes
1answer
200 views

Prove that p is the smallest prime that divides (p-1)!+1

By Wilson's Theorem, we know that p divides (p-1)!+1. Assume there exists another prime d divides (p-1)!+1 and $d<p$. Then $ (p-1)!\equiv-1\mod(d)$. I am not sure if I am right in the following ...
1
vote
0answers
25 views

number of residues modulo $2^n$

I am looking at Walter D. Stangl's paper "Counting Squares in $\mathbb{Z}_n$", and I have a question about the following part of a proof: My question is why must $c \equiv 2^{n-1} \pm b \mod 2^n$? ...
1
vote
0answers
92 views

Need a proofreading why all the units are satisfied $a^2-2b^2 =\pm1$ for $\mathbf{Z}[\sqrt{2}]$

All the units are satisfied Pell's equation $a^2-2b^2=\pm1$ for $\mathbf{Z}[\sqrt{2}]$, $a,b\in\mathbf{Z}$. Here is my proof: Let $a+b\sqrt{2}$ be a unit $\in\mathbf{Z}[\sqrt{2}]$. This implies ...
2
votes
1answer
58 views

Question In Elementary Number Theory Chapter about Euler-Phi.

I have a question about in Euler-phi function chapter in the book 'Elementary Number Theory' by David M. Burton(6th Edition) p.145 exercise number 9. The problem is : Let $f(n)$ be the sum of ...
6
votes
0answers
276 views

number of quadratic residues modulo n

Define $f(n)$ to be the number of quadratic residues modulo $n$. I would like to show that $f$ is multiplicative, that is, for any positive integers $m,n > 1$, $f(mn) = f(m)f(n)$ whenever $(m,n) = ...
0
votes
3answers
68 views

Is it right to say that: if $2a+1=2b$ we have a contradiction?

I am trying to prove by contradiction and I have reached the conclusion that $2a+1=2b$. Now I am tempted to say it's a contradiction and call it a night. Is it a contradiction? because one is even and ...
19
votes
10answers
2k views

How to prove that either $2^{500} + 15$ or $2^{500} + 16$ isn't a perfect square?

How would I prove that either $2^{500} + 15$ or $2^{500} + 16$ isn't a perfect square?
1
vote
2answers
40 views

finding large primes

I was wondering if anyone proved about a specific a number that it has to have a prime factor bigger than the currently largest known prime, without specifying how to find this factor, would it be an ...
1
vote
2answers
55 views

Chinese Remainder Theorem with coprime congruences

Suppose that $(a,m)=1$ and $(b,n)=1$, where $(x,y)$ denotes the greatest common divisor of $x$ and $y$. Show that if $$ c \equiv a \pmod{m} \\ c \equiv b \pmod{n} \\ $$ then $(c,mn)=1$. I've tried to ...
4
votes
2answers
149 views

Is it necessary to use the axiom of Regularity to prove the successor function being injective?

Basically the problem is that given an inductive set $X$ we can define the successor function on $X$ such that $S:X\longrightarrow X$ and for all $x\in X$, $S(x)=x\cup \{x\}$. So, one of Peano axioms ...
5
votes
2answers
89 views

Proof that b is not divisible by 6

$$b=\left \lfloor (\sqrt[3]{28}-3)^{-n} \right \rfloor$$ The brackets mean that the number is the largest integer smaller than $(\sqrt[3]{28}-3)^{-n} $ Proof that b is never divisible by 6. I have ...
2
votes
1answer
18 views

Showing an induction step for a congruence relation.

Let $a$ be an odd integer such that $a^{2^{n-2}}\equiv 1\; \mod {2^{n}}$. I want to show that $a^{2^{n-1}}\equiv 1\; \mod {2^{n+1}}$. My try: The integer $a^{2^{n-1}}$ is obtained from ...
4
votes
0answers
49 views

prime factorization of values of $(n+a_1)(n+a_2)\cdots(n+a_9)$

For the 9 distinct positive integers $a_1$, $a_2$, ..., $a_9$, we look at the polynomial $$p(n) = (n+a_1)(n+a_2)\cdots(n+a_9).$$ Prove that for any $a_1,a_2,\dots, a_9$, there exists a number $N$ for ...
1
vote
1answer
26 views

Question about Schnirelmann Density and Sumset: if $d(A) \ge \frac{1}{2}$ and $d(B) > 0$, wouldn't $d(A+B)=1$

I've been thinking about the Schnirelmann Density and I think that I may still be confused about SumSet and Density. It seems to me that if $d(A) \ge \frac{1}{2}$ and $d(B) > 0$, then $d(A+{B}) = ...
0
votes
2answers
80 views

How to prove that $(3+2\sqrt{2})^n=a_n+b_n\sqrt{2}$ for some positive integers $a_n,b_n$ without induction?

I have to prove that without induction: Let $n$ is non-negative integer number, prove that: $(3+2\sqrt{2})^n=a_n+b_n\sqrt{2}$ where $a_n, b_n$ are positive integer number My try: $a_1=3, b_1=2$ ...
3
votes
2answers
102 views

Find all the positive integer

Find all the positive integers (x,y), such that a) $1!+2!+3!+\cdots+ x!=y^2$ b)$1!+2!+3!+\cdots+x!=y^z$
2
votes
3answers
142 views

I need to prove that the product of two numbers equals the product of their gcd and lcm.

I cant prove it. it's just classic number theory, but it's hard. any help??
0
votes
2answers
48 views

6 is a unique number $n$ such that $n-LD(n)^2 = 2$

Let $LD(n)$ be the lowest divisor of $n$ larger than $1$. Let's find all numbers $n$ such that $n-LD(n)^2 = 2$. If $n$ is even then $LD(n) = 2$ and $LD(n)^2 = 4$. Plugging in we get $n-4=2$, so $n=6$. ...
3
votes
1answer
95 views

Schnirelmann Density: if $d(A) + d(B) \ge 1$, does it follow that $d(A+B)=1$

I am still trying to get my head around the basic properties of Schnirelmann Density. If I'm reading PlanetMath.org correctly, it states that if $d(A) + d(B) \ge 1$, then $d(A+B)=1$ Here's the exact ...
1
vote
4answers
161 views

Common factors for all palindromes

For example a palindrome of length $4$ is always divisible by $11$ because palindromes of length $4$ are in the form of: $$\overline{abba}$$ so it is equal to $$1001a+110b$$ and $1001$ and $110$ are ...
3
votes
3answers
87 views

Why does $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1$ have new divisors $59$ and $509$ all of a sudden?

I am a noob when it comes to math so please bear with me. Why $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1$ has $2$ new divisors $59$ and $509$. I mean, all of its divisors are prime factors and ...
1
vote
2answers
209 views

Find all triples of positive integers (x,y,z) such that

Find all triples of positive integers (x,y,z) such that $x^{z+1} \ - \ y^{z+1}=2^{100}$ The RHS is even, then x and y must be odd and $x^{z+1}>y^{z+1}$, but how to find out them all ?