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

learn more… | top users | synonyms

4
votes
1answer
154 views

Existences of enough integers which can be properly represented by a primitive binary quadratic form

Let $F = ax^2 + bxy + cy^2$ be a binary quadratic form over $\mathbb{Z}$. We say $D = b^2 - 4ac$ is the discriminant of $F$. It is easy to see that $D \equiv 0$ (mod $4$) or $D \equiv 1$ (mod $4$). If ...
23
votes
2answers
1k views

When is a sum of consecutive squares equal to a square?

We have the sum of squares of $n$ consecutive positive integers: $$S=(a+1)^2+(a+2)^2+ ... +(a+n)^2$$ Problem was to find the smallest $n$ such, that $S=b^2$ will be square of some positive integer. I ...
3
votes
1answer
65 views

Show that we can compute the product $n = \Pi_in_i$ in time $O(len(n)^2)$ for given integers $n_1,…n_k$ with each $n_i> 1$.

Show that we can compute the product $n = \Pi_i\ n_i$ in time $O(len(n)^2)$ for given integers $n_1,...n_k$ with each $n_i> 1$. I know that we can compute $ab$ in time $O(len(a)len(b))$ courtesy ...
0
votes
2answers
161 views

Partial sums of infinite series

Suppose some constant $k$ can be represented by a non-alternating convergent infinite series whose partial sums are rational, and we assume $k$ is rational, say $p/q$. If we consider a partial sum ...
3
votes
1answer
421 views

Sum of quadratic residues in $[1,p)$ [duplicate]

Possible Duplicate: Find the sum of all quadratic residues modulo $p$ where $p \equiv 1 \pmod{4}$ Show that if $p$ is a prime of the form $4k + 1$, the sum of quadratic residues ($\bmod p$) ...
4
votes
4answers
539 views

Prove that if $(m - 1)! + 1$ is divisible by $m$, $m$ is a prime with $(m - 1)! = 1.2.3…(m - 2)(m - 1)$

$m$ is a positive integer, and $ m > 1$, Prove that if $(m - 1)! + 1$ is divisible by $m$, $m$ is a prime. Solve this by making a contradiction. My english isn't so well. Please help and thank you ...
2
votes
2answers
245 views

count digits up to number n

I am looking for the count of digits up to 1 million. Is there a formula for this? For example, the count of digits where $n = 10$ is $12$: $0 (+1)$ $1 (+1)$ $2 (+1)$ $3 (+1)$ $4 (+1)$ $5 (+1)$ $6 ...
2
votes
1answer
46 views

Length of the least period of a “double” modulo sequence.

What is the length of the smallest period of the following sequence $$f[n] = \left< \left< n \right>_N \right>_M$$ where $\left<n\right>_N$ represents $n \pmod N$. Is there a ...
2
votes
1answer
79 views

Method for determing least period length of sequence that is the sum of two modulo sequences.

How does one determine the length of the smallest period of the following sequence: $$f[n] = \left< n \right>_N - \left< n \right>_M$$ where $\left<n\right>_N$ represents $n \pmod N$ ...
3
votes
1answer
138 views

When does $\lfloor (n-1)x \rfloor + \lfloor x \rfloor = \lfloor nx \rfloor$?

I am trying to find the conditions under which $\lfloor(n-1)x\rfloor + \lfloor x \rfloor = \lfloor nx \rfloor$. The trivial case is whenever $x \in \mathbb{Z}$. If $n = 2$, then $x - \lfloor x \rfloor ...
1
vote
3answers
106 views

Finding all remainders

I need yours help one more time. I have got very hard task to do but i don' know how to do it :) I need to find all possible remainders of $6^n \bmod 9$. It's very important to me :) Thanks for help, ...
1
vote
2answers
83 views

Integer solutions of $p^2 + xp - 6y = \pm1$

Given a prime $p$, how can we find positive integer solutions $(x,y)$ of the equation: $$p^2 + xp - 6y = \pm1$$
1
vote
1answer
273 views

Catalan constant is irrational. What is wrong with this proof?

Assume $G = p/q$ with $q > 1$ where $p$ and $q$ are coprime. Let $k$ be an arbitrary large odd integer s.t. $2k + 1 > q$ and $p/q$ is not a rational multiple of $$s_k = \sum_{n = 0}^k ...
5
votes
2answers
249 views

divisibility and gcd

I have a positive integer $g$ such that $g$ is the least linear combination of the integers a and b. I have shown $g$ | $h$ ( where $h$ is an arbitrary linear combination of a and b, thus g divides ...
3
votes
4answers
205 views

Proving Congruence Modulo

If $x$ is positive integer, prove that for all integers $a$, $(a+1)(a+2)\cdots(a+x)$ is congruent to $0\!\!\!\mod x$. Any hints? What are the useful concepts that may help me solve this problem?
1
vote
2answers
87 views

Find $y=\sqrt{x}$ where $x$ and $y$ positive integers in polynomial time?

Let $x$ be a positive integer and let $y$ be a real number such that $$y=\sqrt{x}$$ Objectives: If $y$ is an integer, find it in polynomial time. If $y$ is not an integer, prove that there is no ...
-3
votes
2answers
223 views

Is $7^{6n}-6^{6n}$ always divisible by $13$,$127$ and $559$, for any natural number $n$?

Is $7^{6n}-6^{6n}$ always divisible by $13$,$127$ and $559$, for any natural number $n$? $7^{6n}-6^{6n}={(7^{3n})}^{2}-{(6^{3n})}^{2}$ ${(7^{3n})}^{2}-{(6^{3n})}^{2}=(7^{3n}+6^{3n})(7^{3n}-6^{3n})$ ...
1
vote
6answers
959 views

Proving that $a,n$ and $b, n$ relatively prime implies $ab,n$ relatively prime

Question: Suppose $a,b \in \Bbb N$, $\gcd (a,n) = \gcd(b,n) = 1$. The question is to prove or give a counterexample: $\gcd(ab,n) = 1$. My Work: This is what I have so far (for $\alpha, \beta, ...
4
votes
4answers
292 views

$n+1$ is a divisor of $\binom{2n} {n}$

I want to show that $n+1$ is a divisor of $\displaystyle\binom{2n} {n}$, for all $n\in\mathbb{N}.$ I have tried to show it by induction and Pascal's rule but it did not worked out. I would ...
3
votes
2answers
532 views

Euclid lemma by induction

How to prove a generalized Euclid lemma par induction after proving Euclid lemma? I want to prove the generalized lemma, to prove by rearranging the product of number and use Euclid lemma as a model. ...
20
votes
8answers
815 views

If $a$, $a+2$ and $a+4$ are prime numbers then, how can one prove that there is only one solution for $a$?

If $a$, $a+2$ and $a+4$ are prime numbers then, how can one prove that there is only one solution for $a$? when, $a=3$ we have, $a+2=5$ and $a+4=7$
2
votes
0answers
70 views

If $a = p^fb$ and $p \nmid b, 0 \leq f < e$, how many solutions exist for $z^2 \equiv a\ (mod\ p^e)$

For an odd prime $p$, if $a = p^fb$ and $p \nmid b, 0 \leq f < e$, how many solutions exist for $z^2 \equiv a\ (mod\ p^e)$. I have already proved the previous part of this question which was to ...
2
votes
1answer
127 views

Does the theorem work for even primes (i.e. p=2)

In a question, it was asked to prove that if $p$ is an odd prime, $n>0$ and $0<k<p^n$, and $\gcd(k,p)=1$, then $${p^n\choose k}\equiv 0 \pmod {p^n}$$ My question is, is the hypothesis $p$ ...
0
votes
2answers
425 views

Recursive number of divisors function

Does there exist a recursive function, or a recurrence relation, for the number-of-divisors function? For example, something like this: $\sigma_0(n) = \sigma_0(n-1) + \sigma_0(n-2)$
0
votes
2answers
1k views

How to perform logical inclusive OR operation on hexadecimal numbers?

In logic there is so called OR operation that is quite clear to me as long as it is in the binary system. For example, if I want to OR such binary values as "101" (which corresponds to decimal "5") ...
3
votes
3answers
2k views

Prove that if $n$ is not the square of a natural number, then $\sqrt{n}$ is irrational. [duplicate]

Possible Duplicate: $\sqrt a$ is either an integer or an irrational number. I have this homework problem that I can't seem to be able to figure out:Prove: If $n\in\mathbb{N}$ is not the ...
3
votes
1answer
106 views

Determining when $1^N, 2^N, \ldots, k^N$ are divisors of $k!$

Suppose $N$ is a large integer and let $k$ be an integer s.t. $k > N$. Under what conditions can we conclude that $1^N, 2^N, \ldots, k^N$ are all divisors of $k!$?
1
vote
1answer
74 views

For $n=pq$, show that there exist $\alpha, \beta \in Z_n^*$ such that $\alpha, \beta \notin (Z_n^*)^2$ and $\alpha \cdot \beta \notin (Z_n^*)^2$.

For $n=pq$, where p,q are distinct odd primes show that there exist $\alpha, \beta \in Z_n^*$ such that $\alpha, \beta \notin (Z_n^*)^2$ and $\alpha \cdot \beta \notin (Z_n^*)^2$. Here if we try to ...
3
votes
2answers
238 views

All pairs (x,y) that satisfy the equation $xy+(x^3+y^3)/3=2007$

How we can find the all pairs $(x,y)$ from the integers numbers ,that satisfy the equation : $$xy+\frac{x^3+y^3}{3} =2007$$
0
votes
3answers
188 views

If prime $p \equiv 1\pmod 4$ and $b = ((p-1)/2)!$ then show that $b^2 \equiv -1\pmod p$. [duplicate]

This question is from Victor Shoup's book on number theory chapter 2. The problem statement is as mentioned in the title of the question. I haven't been able to crack this one till now. I focused on ...
1
vote
4answers
315 views

how can one find the value of the expression, $(1^2+2^2+3^2+\cdots+n^2)$ [duplicate]

Possible Duplicate: Proof that $\sum\limits_{k=1}^nk^2 = \frac{n(n+1)(2n+1)}{6}$? Summation of natural number set with power of $m$ How to get to the formula for the sum of squares of first n ...
0
votes
5answers
491 views

Every odd composite $=$ prime ${}+ 2x^2$

I was looking through some project-euler questions and I came across one that said Every odd composite number can be written as the sum of a prime and twice a square...This was proven false. ...
6
votes
1answer
338 views

Number of triples $(a,b,c)$ of positive integers such that $\frac{1}{a}+\frac{1}{b}+\frac{1}{c}=\frac{3}{4}$?

What is the number of triples $(a,b,c)$ of positive integers such that $\frac{1}{a}+\frac{1}{b}+\frac{1}{c}=\frac{3}{4}$ is: A) $16$ B) $25$ C) $31$ D) $19$ E) $34$ Note: ...
3
votes
3answers
168 views

Is any Mersenne number $M_p$ divisible by $p+2$?

More precisely, does there exist a natural number $p$ such that $(2^p-1)/(p+2)$ is also a natural number? It seems to me that this is a really simple problem (with the answer "no"), but I couldn't ...
0
votes
1answer
71 views

Find period of reciprocal $1$/$x$? [duplicate]

Possible Duplicate: Compute the period of a decimal number a priori How to find the period of a reciprocal $1$/$x$ ? in both cases when it is terminating i.e (the distinct prime factors of ...
1
vote
1answer
272 views

How to solve Pell's equation $x^2 - Dy^2 = 1$?

How can I solve Pell's equation? $$x^2 - Dy^2 = 1$$ In fact I need some sort of a systematic way that I can translate into a C++ code.. Of course by solving I mean : "smallest positive integer set". ...
1
vote
2answers
133 views

Use a particular method to prove if $a^n \mid b^n$ then $a\mid b$

A question in my tutorial asks to use the fact (can be used without proof) that $(a,b)=(a,c)=1 \Rightarrow (a,bc)=1$ to prove: if $a^n \mid b^n$ then $a\mid b$. I did the following, but my ...
0
votes
1answer
155 views

Finding the maximum remainder of a division

What is the remainder of the following division: $$\frac{(x-1)^y + (x+1)^y}{x^2}$$ For what values of $y$ will the remainder be maximized? (Before anyone asks, NO this is not project euler)
0
votes
3answers
89 views

question related to divisibility

how to prove the following: if $a$ and $b$ are both odd integers, prove: $$a^4 +b^4 \equiv 2 \pmod{16}$$ If anybody know any other method or solution other than putting $a$ or $b = ...
1
vote
1answer
126 views

What is the zeta function of the projective line over $\mathbb{Q}$

What is the zeta function of $\mathbb{P}^1_{\mathbb{Q}}$? Thanks
2
votes
3answers
288 views

remainder problem based on 5 and 7

When a number is divided by 5 than remainder is 2 and when the same number is divided by 7 remainder is 4. What will be remainder be when the same number is divided by 35? What is the concept ...
2
votes
1answer
85 views

Generating integer solutions to $4mn - m^2 + n^2 = ±1$

How can I generate positive integer solutions to $m$ and $n$ that satisfy the equation: $4mn - m^2 + n^2 = ±1$, subject to the constraints that $m$ and $n$ are coprime, $m-n$ is odd and $m > n$.
1
vote
2answers
104 views

Validity of a proof of a mod identity

So I constructed this proof that for any integers $a, c\text{ and }n$, with $n > 1$, if $a ≡ c \pmod n$ then for any integer $m, a^m ≡ c^m \pmod n$. Proof: $a ≡ c \pmod n$ implies that $a ...
23
votes
4answers
1k views

Is the statement “1/3 of the natural numbers are divisible by 3” true? Is anything similar to it true?

If we're talking about a finite set of the natural numbers, like those between 1 and 500 or 1 and a million, it seems to me that the fraction of numbers in that finite set that have a factor of 5 ...
0
votes
3answers
218 views

Periodic Function - Repeating Pattern Problem

For the following question: A necklace is made by stringing N individual beads together in the repeating pattern of Red Bead , Green Bead , White , Blue and Yellow Bead. If necklace begins ...
1
vote
1answer
122 views

Elementary Number Theory $(a+b,\frac{a^p+b^p}{a+b})=1 \text{ or } p$

Assume $(a,b)$=1, and let $p$ be an odd prime, prove that $$(a+b,\frac{a^p+b^p}{a+b})=1 \text{ or } p$$. I thought of letting $p=2k+1,k\in\mathbb{Z}$, then use the identity ...
1
vote
1answer
79 views

Proof for length of period in simple modulo $N$ sequence.

I am looking for a concise proof that the length of the smallest period of the sequence $$f[n] = a n \pmod N $$ is $N$ if $(a,N) = 1$. From the Pigeonhole Principle, it is not hard to show that ...
1
vote
3answers
613 views

Wilson's theorem related problem

prove $$18! \equiv -1 \pmod{437} $$ I do not want full solution to the above problem but if anybody can tell me how we can approach to it, I will really appreciate that.
4
votes
5answers
912 views

Proving $n^4 + 4 n^2 + 11$ is $16k$

if $n$ is an integer , prove that $n^4 + 4 n^2 + 11$ is of the form $16 k$. And I went something like: $$\begin{align*} n^4 +4 n^2 +11 &= n^4 + 4 n^2 + 16 -5 \\ &= ( n^4 +4 n^2 -5) ...
2
votes
2answers
85 views

Infinite descent

This Wikipedia article of Infinite Descent says: We have $ 3 \mid a_1^2+b_1^2 \,$. This is only true if both $a_1$ and $b_1$ are divisible by $3$. But how can this be proved?