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

learn more… | top users | synonyms

-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
21 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
48 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
38 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
24 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
665 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
125 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
78 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
57 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
59 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
35 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
52 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
41 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 ...
4
votes
3answers
125 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
59 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
33 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
41 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
81 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
80 views

Find all values that make the expression a perfect cube [closed]

Find all the positive integers $n$ such that $n^3-n$ is a perfect cube.
3
votes
1answer
42 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
26 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
36 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
78 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
93 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
43 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
176 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
30 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
17 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
40 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
43 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!
1
vote
1answer
39 views

How to calculate the number of lattice 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
59 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
212 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
30 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 ...
0
votes
2answers
23 views

Find possible values in perfect square problems

If P+45 and P+136 are two perfect squares, Then how many possible values of P may exist? Given P is an integer
1
vote
2answers
50 views

To find the right most non zero digit

When expanded 30! ends in 7 zeroes. Find the first non zero digit from right?
1
vote
2answers
28 views

remainder, quotient problem [closed]

If a number is divided by 2010, the quotient and remainder are equal. Find the sum of all such positive integers.
0
votes
0answers
35 views

another series problem [duplicate]

I need help in simplification below are the two formulas for AGP series: if $n$ is even $a\cdot r^{(n-1)/2} + d\cdot( 1 + r + r^2 + r^{(n-1)/2})$ if $n$ is odd $a\cdot r^{(n-1)/2} + d\cdot( 1 + ...
3
votes
0answers
70 views

Does the special Pell equation $X^2-dY^2=Z^2$ have a simple general parameterization?

In Carmichael's Diophantine Analysis ($\S8$), he notes that the equation $$X^2-dY^2=Z^2 \qquad(\dagger)$$ has a two-parameter solution $$x=m^2+dn^2, \quad y=2mn, \quad z=m^2-dn^2. \qquad(\star)$$ He ...
0
votes
3answers
38 views

Proving existence of multiplicative inverses for certain sets with multiplication defined modulo $ n $

Let $ Z_n=\{0,1,2...n-1\}$ and multiplication be defined modulo $n$ . I have to find the $n$s for which all non zero elements of $Z_n$ have a "multiplicative" inverse from within $Z_n$. I conjectured ...
0
votes
4answers
43 views

Is it true that $a*b$ is maximal iff a=b? How to prove it [closed]

I was wondering if this is a known fact in math... How can it be proven?
0
votes
0answers
40 views

need help in simplification

I need help in simplification below are the two formulas for AGP series: if $n$ is even $a\cdot r^{(n-1)/2} + d\cdot( 1 + r + r^2 + r^{(n-1)/2})$ if $n$ is odd $a\cdot r^{(n-1)/2} + d\cdot( 1 + ...
1
vote
1answer
58 views

Polynomial producing only primes

The polynomial: $$a_n x^{n}+a_{n-1}x^{n-1}+\dots+a_{1}x+a_{0}$$ Coefficients ai are natural numbers, the claim is once you substitute the positive integers 1,2,3,... for $x$ the values of the ...