Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.
1
vote
0answers
22 views
Prove $(a,b,c)=((a,b),(a,c))$
The notation is for the greatest common divisor. I know that
$$(a,b,c)=((a,b),c)=((a,c),b)=(a,(b,c))$$
Suppose $g=(a,b,c)$. Then $g|a,b,c$. Also, $g|(a,b),c$ and $g|(a,c),b$. Thus there exist ...
0
votes
1answer
18 views
Showing $p|(a^2 +c^2)$ given $p|(a^2+b^2)$ and $p|(b^2+c^2)$
I had no trouble showing this for $a^2-c^2$ but I'm running into a wall here.
A couple of routes that I took.
1) $p|(a^2+b^2) \Rightarrow \exists{k}\in\mathbb{Z}$ s.t. $a^2+b^2 =pk$
$p|(b^2+c^2) ...
0
votes
1answer
26 views
An Inequality Involving Prime Numbers
Let $p_i$ be the $i^{th}$ prime number. It seems as though the following inequality is true for all positive integers $m$ and real numbers $x>1$:
...
1
vote
3answers
80 views
Notation for the least common multiple
Suppose I use the notation $\{a,b \}$ for the least common multiple of integers $a$ and $b$. Is this common notation in number theory (it is from Hardy and Wright), and would a mathematically literate ...
0
votes
3answers
35 views
Identity involving LCM and GCD
Let $(a,b)$ denote the GCD of $a$ and $b$, and let $[a,b]$ denote the LCM of $a$ and $b$. Prove $\frac{[a,b,c]^2}{[a,b][b,c][c,a]}=\frac{(a,b,c)^2}{(a,b)(b,c)(c,a)}$.
4
votes
3answers
201 views
Proving an expression is composite
I am trying to prove that $ n^4 + 4^n $ is composite if $n$ is an integer greater than 1. This is trivial for even $n$ since the expression will be even if $n$ is even.
This problem is given in a ...
0
votes
1answer
22 views
Examples of (use of) position-systems
As you now, the most used number system is the position system with base 10, where for instance $101$ means $1\cdot 10^2+0\cdot 10^1 + 1 \cdot 10^0$. Likewise we can define binary number system with ...
0
votes
1answer
33 views
Count pairs with odd XOR
Given an array A1,A2...AN. We have to tell how many pairs (i, j) exist such that 1 ≤ i < j ≤ N and Ai XOR Aj is odd.
Example : If N=3 and array is [1 2 3] then here answer is 2 as 1 XOR 2 is 3 ...
1
vote
0answers
47 views
Has this weaker version of Fermat's last theorem already had an elementary proof?
Recently I carried out an elementary proof of the following assertion, which is a special case of Fermat's last theorem:
If
$p$
is an odd prime and
$x, y, z > 0$
are integers such that
$(x, y) = ...
-1
votes
1answer
28 views
$p$ and $q$ are primes. Prove $\forall n,k\in \mathbb N, (p^n\mid q^k⇒p=q)$ [duplicate]
I'm having trouble answering this question, can anyone help explain a full solution of this problem? I will be very grateful. Thanks!
0
votes
3answers
19 views
Let n and k be positive integers. If n ≥ (k + 1), then n! + (k + 1) is a composite number
I've been having trouble with finding the proof for this question. Can anybody explain the solution to me? Thanks so much!
0
votes
2answers
45 views
Question regardles primes and the fundamental theorem of arithmetic
I have been reading through my book of practice proofs and came across this particular question which has stumped me.
$p$ and $q$ are primes. Prove $\forall p \in \mathbb{Z}, \forall k \in ...
0
votes
2answers
29 views
Show if (m,n) = 1, then for any # p, we have (p,mn) = (p,m)(p,n).
Show that if $(m,n) = 1$, then for any number p, we have $(p,mn) = (p,m)(p,n).$
1
vote
1answer
18 views
Reduced Residue System in Mathematica
How can I create the standard reduced residue system modulo $m$ in Mathematica for a given positive integer $m$? For example, if I input $10$, I would like it to give me the list $\{1,3,7,9\}$. ...
7
votes
5answers
625 views
Induction hypothesis misunderstanding and the fundamental theorem of arithmetic.
The fundamental theorem of arithmetic is made of two parts:
The existence part:
There exist primes
such that for any natural number $j$, we can write $j$ as a product of prime numbers.
The ...
1
vote
1answer
77 views
Divisibility problem incorrect proof
here's the problem:
Find all odd integers $n$ greater than $1$ such that for any relatively prime divisors $a,b$ of $n$ the number $a+b-1$ is also a divisor of $n$.
And this is my proof (which I ...
1
vote
3answers
75 views
Find the remainder of $\frac{1! +2!+\, \dots\, +95! }{15}$.
I think I found my answer but I am looking for better ones
0
votes
0answers
51 views
2 player team knowing maximum moves
Given a list of N players who are to play a game. Each of them are either well versed in a move or they are not. Find out the maximum number of moves a 2-player team can know.
And also find out how ...
1
vote
1answer
53 views
Proof that $a\equiv b \pmod n \iff a \pmod n = b\pmod n$
Proof that for every $a,b \in \mathbb Z,\ n \in \mathbb N$, that
$$a\equiv b \pmod n \iff a \pmod n = b \pmod n.$$
My approach is:
$n\mid a$ and $n\mid b$
$a\equiv b \pmod n \iff \exists x,y: ...
2
votes
0answers
34 views
Arithmetic progressions of Perfect squares [duplicate]
It is well known that the exists no arithmetic progression of squares of length 4. But I could not find a simple proof. please can you help me.
0
votes
1answer
42 views
Rearranging terms in a series
I am considering the limit of the sum S of an alternating series $p_1,n_1, p_2,n_2, p_3,n_3…$ where $p_n$ are positive and $n_n$ negative terms. If the limit exist = P of the sum of the positive terms ...
0
votes
2answers
40 views
$A^7 \not\equiv A(\mod 13) \Rightarrow A^{78} + 1 \equiv 0 (\mod 169)$
Let variable $A$ is integer and $A^7 \not\equiv A(\mod 13)$.
Prove that $A^{78} + 1 \equiv 0 (\mod 169)$
Could someone explain, how to solve this type of problems?
Any help would be greatly ...
3
votes
2answers
104 views
Interesting behavior of $\frac{n}{v_2(n!)+1}$.
I've lately noticed some interesting behavior from the values of the function $f(n)=\frac{n}{v_2(n!)+1}$,
Where $v_p(n)$ is the $p$-adic valuation of $n$, and we also know that ...
0
votes
2answers
55 views
How to solve $ \prod \limits_{i=1}^{99}[i]_{100} $
Solve: $\prod \limits_{i=1}^{99}[i]_{100}=?$
Due to the fact that i is always smaller than 100, I assume I can solve this example just by multiplying the following values: $1*2*3*4*5…*98*99$ ? ...
0
votes
1answer
30 views
How solve $[20]_3^{-1}$?
What does this mean, $[20]_3^{-1}$? it's from the topic rings, fields and residue classes.
Can you give me a hint how to solve this?
3
votes
1answer
40 views
Theorem on Giuga number
Giuga number : $n$ is a Giuga number $\iff$ For every prime factor $p$ of $n$ , $p | (\frac{n}{p}-1)$
How to prove the following theorem on Giuga numbers
$n$ is a giuga number $\iff$ ...
2
votes
0answers
73 views
Questions about central polygonal numbers $1, 2, 4, 7, 11, 16, 22, 29, 37, 46,\cdots$
Formula for Central polygonal numbers is $\frac{n(n+1)}{2} + 1$, if $n=1$ or $n$ is prime, we get the new sequence $A$:
2, 4, 7, 16, 29, 67, 92, 154, 191, ...
It seems that all primes either is ...
1
vote
3answers
68 views
Find all values that make the expression a perfect cube [on hold]
Find all the positive integers $n$ such that $n^3-n$ is a perfect cube.
3
votes
1answer
33 views
Can a Mersenne number be a power (with exponent > 1) of a prime?
Let $n \geq 1$ and consider the (Mersenne) number $M_n = 2^n-1$. Is it possible that $M_n = p^k$ for some prime $p$ and some (necessarily odd) $k > 1$? Thanks in advance.
2
votes
1answer
25 views
Divisors of at least one of three numbers
Question: Find the number of positive integers that are divisors of at least one of $10^{10}$, $15^7$, $18^{11}$.
My solution (my answer was wrong): I thought that the numbers that are divisors of at ...
0
votes
1answer
25 views
Game of coins with two players
Two Players play a game as follow : Given total N coins where x coins are of red color and y coins of blue color.
Now Player1 selects a coin from the heap of coin and put it in a line on table. Then, ...
2
votes
1answer
42 views
LCM and GCD equation
Let $a$, $b$, $c$ be three positive integers such that
$$\mathrm{lcm}(a,b)\cdot\mathrm{lcm}(b,c)\cdot\mathrm{lcm}(c,a)=a\cdot b\cdot c\cdot \gcd(a,b,c).$$
Given that none of $a$, $b$, $c$ is an ...
4
votes
2answers
88 views
Powers and differences of positive integers
Assume that $a$, $b$, $c$, and $d$ are positive integers such that $a^5=b^4$, $c^3=d^2$, and $c-a=19$. Determine $d-b$.
I know this question isn't particularly hard, but I've been having trouble ...
0
votes
1answer
21 views
Position of switches based on divisibility
There is a set of $1000$ switches. Each has four different positions, called $A$, $B$, $C$, and $D$. When the position of any switch changes, it is only from $A$ to $B$, from $B$ to $C$, from $C$ to ...
2
votes
1answer
31 views
Sum of certain integers $a$ where $a^6$ does not divide $6^a$
Find the sum of all positive integers $a=2^n3^m$ where $n$ and $m$ are non-negative integers, for which $a^6$ is not a divisor of $6^a$.
3
votes
1answer
26 views
For every positive number $n$, there exists a $n$ digit number having all odd digits and divisible by $5^n$
Prove that for every positive integer $n$, there exist a $n$ digit number, divisible by $5^n$, whose all digits are odd. for example,
for $n=1, 5$
$n=2,75$
$n=3, 375$.......
I have no idea how to ...
4
votes
2answers
40 views
Solving congruences
I've the following congruence system:
\begin{align*}
I \quad 2x \equiv 0\mod 7 \\
II \quad x \equiv 1 \mod 5\\
III \quad x \equiv 3 \mod 4
\end{align*}
Now I tried to solve it:
\begin{align*}
II ...
5
votes
2answers
169 views
How many diamonds did they steal?
There are $7$ thieves. They steal diamonds from a diamond merchant and run away into the jungle. Whilst they're running, night falls and they decided to rest in the jungle. When everybody is ...
2
votes
0answers
27 views
Does the inverse of Euclids Pythagorean equation hold?
I know that one can generate many Pythagorean triples $(A,B,C)$, where $C^2=A^2+B^2$ with Euclid's formula: $C=X^2+Y^2$, $A=X^2-Y^2$, and $B=2 X Y$.
Euclid's formula can find all primitive ...
0
votes
0answers
14 views
to maximize the summation
let F=$∑i=1$ to $N$ $((abs(A[i]-X))^P mod $K$)mod K$
$A[1..N]$ is an array with $N$ elements, the problem is to find $X$ such that the above summation F maximized where $X$ can take any value from ...
0
votes
1answer
19 views
Limits on repeated sum in circle method
In Bob Vaughan's book The Hardy-Littlewood Method, early on he gives a sum
\begin{equation}
\left(\sum_{m=1} ^N e(\alpha m^k)\right)^s = \sum_{m_1 = 1} ^N \sum_{m_2 = 1} ^N \cdots \sum_{m_s = 1} ^N ...
0
votes
2answers
62 views
Find all values of for which the ratio is an integer
Find all values of $n$ for which,
$$\dfrac{(\dfrac{n+3}{2}) \cdots n}{(\dfrac{n-1}{2})!}$$
is an integer.
I have tried the problem for some primes. Each time it seemed true. But I still ...
0
votes
1answer
31 views
Sum of divisor and positive divisor problem
The sum of all the positive divisor and the sum of their reciprocals of a number N are $195$ and $\frac{65}{24}$ respectively.
Find N?
1
vote
1answer
41 views
Primes of the form $x^2+ny^2$ where $n\equiv 1\pmod{4}$ is a squarefree number
Let $n\equiv1\pmod{4}$ be a squarefree number and $p\equiv1\pmod{4n}$ be a prime number. Does there exist $x,y\in\mathbb{N}$ such that $p=x^2+ny^2$?
1
vote
1answer
37 views
Multiplicative order of n mod 2n-1
I am trying to find the smallest positive integer k such that
$n^k \equiv 1 \mod(2n-1)$. Has this been solved? Any thoughts or references are greatly appreciated!
0
votes
1answer
22 views
How to calculate the number of points in the interior and on the boundary of these figures with vertices as lattice points?
We define a point $(x,y)$ in the plane to be a lattice point if both $x$ and $y$ are integers.
Now let $$S\colon= \{ (x,y) \ | \ 0 \leq x \leq m, \ 0 \leq y \leq \frac{nx}{m} \}, $$ where $m$ and ...
1
vote
1answer
58 views
Proof by contradiction: logarithm
I need to prove by contradiction that $\log_2(3)$ is irrational.
I'm really unfamiliar with logs to be honest, it's been awhile since I've done them and I'm unsure of how to approach this.
Any help ...
13
votes
2answers
197 views
Integer values of $\frac{x}{y}+\frac{y}{z}+\frac{z}{x}$?
What are the possible integer values of
$$\frac{x}{y}+\frac{y}{z}+\frac{z}{x}$$
where $x$, $y$, and $z$ are positive integers?
My suspicion is the the only integer values are $3$ and $5$, the former ...
1
vote
2answers
60 views
cannot be the value of the expression.
Which of the following can not be the value of $x/y+y/z+z/x$. Where $x$, $y$, and $z$ are positive integers?
a) $4 $
b) $7/2$
c) $3$
d) $5/2$
Should I go through the options?
0
votes
1answer
27 views
What do I do wrong with Möbius method of inversion?
I use the Möbius inversion with polynomials as e.g. in the well-known inversion formula
of the cyclotomic polynomials.
So I have $$p_{2n}(x)=\prod_{d|n}(2q_d(x))^{\mu(\frac{n}{d})}$$
Now I get the ...
