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

learn more… | top users | synonyms (1)

1
vote
5answers
121 views

Sum of elements in the nth set of the sequence of sets of squares $\{1\}$, $\{4,9\}$, $\{16,25,36\}$, …

Let $S_n$ denote the sum of the elements in the $n^{th}$ set of the sequence of sets of squares: $\{1\}$, $\{4,9\}$, $\{16,25,36\}$, $\{49,64,81,100\}$,.... i.e. $S_1 = 1$, $S_2 = 13$, ... How do you ...
2
votes
3answers
229 views

If $5 \times 12 = 104$, how much is $10 \times 11$?

Question is in the title, this is for my analysis course. I don't know where to begin.
-1
votes
2answers
80 views

Show that $z$ is prime if $z|xy$ implies $z|x$ or $z|y$

Let $z$ be an integer greater than or equal to $2$. Suppose for all integers $x$ and $y$ that $z|xy$ implies $z|x$ or $z|y$. Show that $z$ is prime.
4
votes
2answers
147 views

Conjecture involving semi-prime numbers of the form $2^{x}-1$

Let $x$ be a positive integer such that $(2^{x}-1)=pq$ , where $p$ and $q$ are prime numbers. I want to show that either $p^{2} \bmod x \equiv 1$ or $q^{2} \bmod x \equiv 1$ (or both of course). Is ...
5
votes
1answer
82 views

3 incrementing buttons, optimal value

This was asked on PhysicsForums.com and I am very interested in seeing a nice solution. Suppose we want a user to be able to enter any numeric value from 1 to 100. This number is entered by 3 ...
1
vote
1answer
53 views

Find all $n\in\mathbb N$ such that $n\ne k^2$ ($k\in\mathbb N$) and $\lfloor\sqrt{n}\rfloor^3\mid n^2$.

Find all $n\in\mathbb N$ such that $n\ne k^2$ ($k\in\mathbb N$) and $$\lfloor\sqrt{n}\rfloor^3\mid n^2$$ That's a really interesting problem and I can't seem to find an idea for a solution. Some help ...
3
votes
1answer
99 views

Problem in elementary number theory about prime numbers.

I was looking at a packet of problems in elementary number theory, when I saw this question: Show that $n$ is prime iff ...
2
votes
1answer
97 views

Properties of modular arithemtic mod primes and quadratic residues

I have the following two equations: $$z_1 = x_1^2 \pmod p$$ $$z_2 = x_2^2 \pmod q$$ and p and q are prime. and I want to show $x^2$ and $z^2$ are equal mod pq $$x^2 = x_1^2 c_1^2 + x_2^2 c^2_2$$ ...
0
votes
4answers
56 views

I've got a small problem with induction

Let me take a quick example: We want to prove by induction that $3^n-1$ is a multiple of 2, where n is a positive integer. So we start with our "base case" and show that $3^1-1$ is indeed a multiple ...
4
votes
3answers
204 views

If $x\in\mathbb R$, solve $4x^2-40\lfloor x\rfloor+51=0$.

If $x\in\mathbb R$, solve $$4x^2-40\lfloor x\rfloor+51=0$$ where $\lfloor x\rfloor$ denotes the integer part of the number. $\lfloor x\rfloor\le x$ and $\lfloor x\rfloor=x-\{x\}$, where $\{x\}$ ...
7
votes
1answer
231 views

If $p,q$ are prime, solve $p^3-q^5=(p+q)^2$. [duplicate]

If $p,q$ are prime, solve $$p^3-q^5=(p+q)^2$$ I can't think of a nice idea for the solution. Since there's a solution $(7;3)$, consisting of two distinct numbers, I really doubt modular arithmetic ...
1
vote
2answers
55 views

Given two odd primes, $p\neq q$, prove that there are no primitive roots $\mod(pq)$

Given two odd primes, $p\neq q$, prove that there are no primitive roots $\mod(pq)$ I don't know where to start with this, any help would be appreciated.
0
votes
1answer
250 views

Representing whole numbers as $a^2 + b^2 + 4ab$ for integers $a,b$

Lets say it's $18$. Is there a way to be sure that this number can definitely be represented like $$a^2 + b^2 + 4ab$$ The problem mainly arises due to the $4ab$ and not $2ab$, otherwise only perfect ...
3
votes
2answers
85 views

If $x,y\in\mathbb Z$, solve $x^2+xy+y^2=x^2y^2$.

If $x,y\in\mathbb Z$, solve $$x^2+xy+y^2=x^2y^2$$ We could try some factorizations. $x^2+y^2=xy(xy-1)$. We may as well add $2xy$ to both sides: $(x+y)^2=xy(xy+1)$. Then we could subtract $x^2y^2$ ...
3
votes
1answer
312 views

An alternate analysis to the (worst-case) run time of the euclidean algorithm

I was trying to figure out the running time of the euclidean algorithm. The analysis that I found on Wikipedia and CLRS both analyze the run time of the euclidean algorithm using the Fibonacci ...
3
votes
0answers
83 views

Find n's for which $P_n$ is prime.

Consider the numbers $P_n=(3^n-1)/2$. Find $n$'s for which $P_n$ is prime. Conjecture: If $n \equiv 1 \mod 6$, and $n$ is prime, then $P_n$ is prime. I have tried proving this by contradiction but ...
5
votes
5answers
204 views

Intuition of why $\gcd(a,b) = \gcd(b, a \pmod b)$?

Does anyone have a intuition or argument or sketch proof of why $\gcd(a,b) = \gcd(b, a \pmod b)$? I do have a proof and I understand it, so an intuition would be more helpful. The proof that I ...
2
votes
1answer
109 views

A question of divisibility. (NBHM 2012) [duplicate]

The number $18! + 1$ is divisible by 437. How to prove it? I have $(19-1)! + 1 \equiv 0$ (mod 19) and $437 = 19 \times 23$. What to do next? Thank you for your help.
0
votes
2answers
214 views

Find all even natural numbers which can be written as a sum of two odd composite numbers.

Find all even natural numbers which can be written as a sum of two odd composite numbers. Please help in in solving the above problem.
6
votes
1answer
250 views

Does $19,199,1999,\dotsc$ contain infinitely many prime numbers?

Are there infinitely many primes of the form $F_n =2\times10^n-1$? That is, does this sequence, $$19,199,1999,\dotsc$$ contain infinitely many prime numbers? I think about Dirichlet's theorem on ...
2
votes
3answers
114 views

Does this equation have positive integer solutions?

The only solution I can find for $a^2 + b^2 + c^2 = d^2 + e^2 + f^2$ is $a=0$, $b=0$, $c=0$, $d=0$, $e=0$, $f=0$. Are there any positive integer solutions? Any where none of $a,b,c,d,e,f$ are ...
-1
votes
7answers
70 views

If an integer a is such that a-2 is divisible by 3 then a^2-1 is divisible by 3. prove by direct method

How to prove that if a is number such that $a-2$ is divisible by $3$ then $a^2-1$ is divisible by $3$ using direct method. I know if $a = 2$ then $a-2 = 0$ is divisible by $3$ and $2^2-1 = 3$ is ...
2
votes
1answer
94 views

sum of cubes in its own loop ends …

If $n$ is multiple of $3$, then sum of cubes of each digit of $n$ will end at $153$ in certain time. In case, if you got some other number then again apply sum of cubes of each digit of new number ...
6
votes
1answer
59 views

Iterations of modulus operation

While working on a completely unrelated task, I thought up the following problem: Consider the following process. Let $a_0$ and $n$ be given, and determine $a_1,\ldots, a_k$ as follows: ...
3
votes
0answers
121 views

Question about congruence classes and reduced residue systems

Let $x$,$y$ be integers such that the reduced residue system modulo $y$ divides equally into congruence classes modulo $x$. An example of this is $x=4$, $y=5$. The reduced residue system modulo $5$ ...
2
votes
3answers
112 views

If $n,k\in\mathbb N$, solve $3^k-1=x^n$.

If $n,k\in\mathbb N$, solve $$3^k-1=x^n$$ This seems like an interesting problem. I've currently tried a few things (one could try a lot of things in this case): $1)$ $x^n\equiv -1\pmod 3\Rightarrow ...
0
votes
1answer
54 views

If $3n+1$ is a perfect square where $n$ is a positive integer greater than $1$. Then how to prove that $n+1$ would be sum of $3$ perfect squares? [duplicate]

If $3n+1$ is a perfect square where $n$ is a positive integer greater than $1$. Then how to prove that $n+1$ would be sum of $3$ perfect squares?
4
votes
3answers
123 views

If $n,k\in\mathbb N$, solve $2^8+2^{11}+2^n=k^2$. [duplicate]

If $n,k\in\mathbb N$, solve $$2^8+2^{11}+2^n=k^2$$ It's hard for me to find an idea. Some help would be great. Thanks.
11
votes
1answer
157 views

Find all $x,y,z\in\mathbb N$, $x,y,z>1$ such that satisfy $x\mid yz+1$, $y\mid xz+1$, and $z\mid xy+1$

Find all $x,y,z\in\mathbb N$, $x,y,z>1$ such that satisfy $$\begin{cases}x\mid yz+1\\y\mid xz+1\\z\mid xy+1\end{cases}$$ I've found out easily that $$\begin{cases}x\nmid yz\\y\nmid xz\\z\nmid ...
0
votes
1answer
49 views

How Can I find the summation of divisors of $n^p$.

For Example $n=8$ and $p=2$. So $n^p=64$. And the summation of divisors is $1+2+4+8+16+32+64=127$. But the problem arises when $n=10^6$ and $p=10^6$. Remember u can modulus the result by $100$.
0
votes
3answers
36 views

Except the Dividend Itself — Any Divisor is Less than Half of the Dividend

Postulate $d \neq n$ is a divisor, $n$ is a dividend. Why $d \le n/2$? I know the dividend itself is a divisor. $d|n$ is defined as $\exists \; c\in \mathbb{Z}$ such that $dc = n$. ...
1
vote
3answers
46 views

Integers divide several solutions to Greatest Common Divisor equation

I'm not sure about the topic's correctness but my problem is following: Suppose $u_1,v_1$ and $u_2,v_2$ are two different solutions for $au_i + bv_i = 1$, then $a \mid v_2-v_1$ and $b\mid u_1-u_2$. ...
9
votes
1answer
286 views

Alternating sum of remainders

Is there a nice way to evaluate the following for arbitrary positive integers $n,j,L$: $$\sum_{k=1}^{\left[\frac{n-L}{j}\right]}(-1)^{(n-kj)\pmod L}$$ I feel like this should be easy but, I get ...
1
vote
1answer
85 views

There is a positive integer $y$ such that for a polynomial with integer coefficients we have $f(y)$ as composite

Show that if $f(x)=a_nx^n+\cdots a_1x+a_0$ with $a_i \in \mathbb{Z}$, then there is a positive integer $y$ such that $f(y)$ is composite. To prove this, we suppose that $f(x)=p$. Then for $f(x+kp)$ ...
1
vote
2answers
65 views

Show $\gcd (a,b)=\gcd (b,r)$ if $a = bq + r$

Let $a, b$ be two integers with $b \neq 0$, and $q, r$ non-negative integers such that $a = bq + r$. How can we show that $\gcd (a,b)=\gcd (b,r)$?
1
vote
1answer
51 views

Prove that $8.\overline{74}\in\mathbb{Q}$

Prove that $8.\overline{74}\in\mathbb{Q}$ My try :: $8.\overline{74}=a/b\implies b 8.\overline{74}=a$ But in fact i don't know how to prove it, maybe someone will help.
3
votes
1answer
32 views

Prove that $c=\sqrt[x]{\Delta^x/\xi^x+1}\notin \mathbb{N}$

Prove that $c=\sqrt[x]{\Delta^x/\xi^x+1}\notin \mathbb{N}$ where $\Delta,\xi,x\in\mathbb{N}$ How can I prove this? My try:: Assume $\Delta^x/\xi^x$ is an integer then: $\sqrt[x]{s^x+1}$ where $s$ ...
4
votes
1answer
87 views

Find all $x,y\in\mathbb{Z}$ s.t $2x^3-7y^3=3$

Find all $$x,y\in\mathbb{Z}$$ such that $$2x^3-7y^3=3$$ Solution: We consider first $$2x^3-7y^3\equiv3 \pmod 2$$ $$5y^3\equiv 1 \pmod 2$$ $$y^3\equiv 1 \pmod2$$ which has solution $y\equiv 1 ...
3
votes
2answers
82 views

Fast way of calculating the order of an element in $\mathbb{Z}_n$?

Is there a fast way of calculating the order of an element in $\mathbb{Z}_n$? If i'm asked to calculate the order of $12 \in \mathbb{Z}_{22}$ I just sit there adding $12$ to itself and seeing if the ...
0
votes
1answer
33 views

How to count minimum number of pairs satisfying divisibility condition.

Consider the pair of numbers $(x_1, y_1),\, (x_2, y_2),\, (x_3, y_3), \dots$ and so on, each $x$ and $y$ is a natural number. Then what should be the least number of such pairs required, so that we ...
2
votes
2answers
83 views

Quadratic Polynomials over $\mathbb F_p$

I'd like to know a reason why (irreducible) quadratic polynomials over $\mathbb F_p$ do not reach all numbers in $\mathbb F_p$. Example: $f(x)=x^2+3x+1$ in $\mathbb F_7$ is irreducible, i.e has no ...
1
vote
1answer
43 views

Converting Fibonacci number $F_{5n+3}$ to Lucas numbers $L_{n+k}$

I'm trying to prove that$F_{5n+3}\text{mod}10 = L_{n}\text{mod}10$. I rearranged it into a more solvable form of $F_{5n+3}-L_n = 10k$ (because if two numbers end in the same digit, their difference ...
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
4answers
120 views

Stuck while trying to prove $2k^3 \geq (k + 1)^3$…

how can I prove the following: $2k^3 \geq (k + 1)^3$ This is the final part of the elaborate proof for $2^n > n^3 $ give $ n \geq 10$ I have used induction and end up with: $ 2^{K+1} > 2k^3 $ ...
1
vote
4answers
77 views

Is $2k-1 \nmid (k-1)(k-2)$ true for all positive integers $k>2$?

How to prove or disprove that for all integers $k>2$: $2k-1 \not\mid (k-1)(k-2)$ Using computer I've verified it for all integers less than 10000000, but I am not sure whether it holds for ...
1
vote
1answer
102 views

A restatement of my question about the totient function and congruence classes

I appreciate the answer to my previous question, but I still felt my larger question wasn't answered. So, I am attempting to restate the question more clearly. If $x,y$ are integers where $x | ...
2
votes
3answers
57 views

Quadratic congruence relation

Is there a general formula for solving quadratic congruence relation like $ax^2-bx+c = 0$ in $\mathbb{Z}_{n}$ where $n \in \mathbb{N}$? For example, I am trying to solve $x^2-3x+2 = 0$ in ...
4
votes
1answer
79 views

Question about the totient function and congruence classes

If $x,y$ are integers where $x | \varphi(y)$ does it follow that the reduced residue class modulo $y$ divides evenly into congruence classes modulo $x$? For example, if we look at $y=35$ and $x = 3$. ...
9
votes
1answer
111 views

Find all of the integer solutions of $x^3y+y^3z+z^3x=0.$

Using Fermat's Last Theorem, find all of the integer solutions of $x^3y+y^3z+z^3x=0.$ I try to make some substiution so as to transform the equation into a form like a fermat equation but in vain, ...
-3
votes
4answers
2k views

Sum of odd numbers always gives a perfect square. [duplicate]

$1 + 3 = 4$ (or $2$ squared) $1+3+5 = 9$ (or $3$ squared) $1+3+5+7 = 16$ (or $4$ squared) $1+3+5+7+9 = 25$ (or $5$ squared) $1+3+5+7+9+11 = 36$ (or $6$ squared) you can go on like this as far as you ...