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

learn more… | top users | synonyms

4
votes
1answer
154 views

Interesting Sum Congruence

Let $5\mid a$, $\gcd(a,b)=1$, and $b\equiv 2\bmod 5$. How can one show that $\sum_{k=1}^{a}k\lfloor\frac{kb}{a}\rfloor\equiv 2\bmod 5$? Similarly, can we show that if instead $b\equiv 3\bmod 5$, then ...
0
votes
3answers
401 views

Finding the size of a list given its mean, and the mean when one number is added to the list

The mean of a list of $n$ numbers is $6$. When the number $17$ is added to the list, the mean becomes $7$. What is the value of $n$?
0
votes
2answers
49 views

How to find irrational approximates

Say I have a rational number, $n$, that approximates an irrational number of the form: $$n \approx {a+\sqrt b \over c}$$ in terms of being irrational. What is a good way of finding the unknown ...
1
vote
4answers
56 views

Is it possible to do modulo of a fraction

I am trying to figure out how to take the modulo of a fraction. For example: 1/2 mod 3. When I type it in google calculator I get 1/2. Can anyone explain to me how to do the calculation?
0
votes
1answer
34 views

Maximum value of function involving factorials

Define $$g_{(k,j)} = \frac{a^{n-k}b^k(k+n)!x^{k+n-j}}{k!(n-k)!(k+n-j)!}$$, where $n,k,j \in \Bbb{N}$ are fixed such that $(0 \leq x \leq a/b ),(b<a),(0 \leq k \leq n ),(2 \leq j \leq 2n),(0 \leq ...
6
votes
1answer
87 views

Finding all such polynomials under a gcd condition

Find all such polynomial $f(x)\in \mathbb{Z}[x]$ such that $$ \forall n\in \mathbb{N} \quad \gcd(f(n),f(2^n))=1$$ This is a problem from the Indian Team Selection Test. Can someone give me a solution ...
1
vote
0answers
107 views

Evaluate this product $n \times \frac{n-1}{2} \times \dots \times \frac{n-(2^k-1)}{2^k}$

For $k = \lfloor \log_{2}(n+1) \rfloor - 1$ evaluate $n \times \frac{n-1}{2} \times\frac{n-3}{4} \times \frac{n-7}{8} \times \dots \times \frac{n-(2^{k}-1)}{2^k}$ So the product goes up to $k$ and I ...
-1
votes
0answers
58 views

Sum of possible permutations

Lets call two arrays A and B with length n almost equal if for every i (1 <= i <= n) CA(A[i]) = CB(B[i]). CX[x] equal to number of index j (1 <=j <= n) such that X[j] < x. For two ...
4
votes
1answer
109 views

Congruence modulo

Let $p$ be the prime number bigger than $2$. Prove that $\dfrac{2^p-2}{p}\equiv 1-\dfrac{1}{2}+\dfrac{1}{3}-\dots-\dfrac{1}{p-1} \pmod p$ I do not know where to even start
1
vote
1answer
50 views

Other Interesting solutions to $a=bq+r$? [closed]

The division algorithm says $a=bq+r$, with $r$ between $0$ and $b$. Are there interesting restrictions on $r$ using number-theoretic properties that make the equation $a=bq+r$ hold, or hold with ...
2
votes
1answer
90 views

Solutions to a diophantine equation

I tried to find integer solutions to the following diophantine equation $$x^3 - 3y^3 + 5z^3 - 3xy^2 + 3x^2y + 9xz^2 + 7x^2z + 3yz^2 - 3y^2z + xyz = 0$$ but was unable to do so. I suspect that there ...
4
votes
2answers
62 views

prove that $\phi(xy) =\phi(x)\phi(y)$ for any $x$ and $y$ with $(x, y) = 1$. [duplicate]

Prove that $\phi(xy) = \phi(x) \phi(y)$ for any $x$ and $y$ with $(x, y) = 1$. I understand the concept, and have done several examples proofing this but cannot put it in "proof form" because unless ...
7
votes
0answers
116 views

Infinite sum involving $q$-adic representations of whole numbers and $q$-factorial numbers

Let $q \in \mathbb{N}_{\geq 2}$. For $n \in \mathbb{N}_0$, let $$\mathrm{fac}_q(n) := \prod_{i=1}^n (1+q+\dots+q^{i-1}) = \prod_{i=1}^n \frac{q^i-1}{q-1}$$ be the $q$-factorial of $n$. In particular, ...
0
votes
3answers
47 views

SAT elementary number theory

If $0 < pt < 1$, and $p$ is a negative integer, which of the following must be less than $–1$? A. $2p$ B. $2t$ I think $t<0$ so both $2p$ and $2t$ must be less than $-1$. The answer is A. ...
0
votes
0answers
15 views

Binomial coefficients modulo prime

Let $p$ be prime number bigger than 2 and $a$ is integer such that $0<a<p-1$. Prove that $C_{p-1}^{a}\equiv 1\pmod p$. Please help
2
votes
1answer
43 views

Infinite sets and arithmetic progressions [closed]

If $S\subset\mathbb N$ is infinite, prove that we can find $p,q\in\mathbb N$, such that either whenever $ n\equiv p\pmod q$, we have$$ n\in S $$ or else whenever $n\equiv p\pmod q$, we have $$ ...
0
votes
2answers
49 views

Integral values and reducibility of fractions

Find all integers $n$ such that $$\frac {3n+4}{n+2}$$ is also an integer. I started substituting integral values except $n=-2$ but I could not reduce
0
votes
1answer
35 views

Integer product problem

Find all integers n for which the number $$(n+3)(n-1)$$ is also an integer I tried. According to me for any replacement of n by integer $$(n+3)(n-1)$$ produces integer. What is the right argument?
2
votes
5answers
67 views

Lowest form of rational number

Suppose $\frac pq$ is a positive rational in its lowest form, prove that ${\frac1q}+{\frac{1}{p+q}}$ is also in the lowest form I tried with the Least common multiple of the denominators and it was ...
-1
votes
4answers
50 views

How many divisors are there in 2015, that is d(2015)? [closed]

This is the question raised in our class to check our understanding in divides.
2
votes
1answer
52 views

Understanding Hensel's Lemma

I am learning Hensel's Lemma and trying to solve the polynomial congruence $$x^5+x^4+1\equiv 0\pmod{81}$$ Now my professor taught us the technique of building up from $p$, to $p^2$, and continuing to ...
1
vote
1answer
49 views

PowerMod: Solving for the base

Given the problem $c^d \mod n = m$ and values for $d$, $n$, and $m$, how would one solve for $c$? A general solution or approach would be fine, as well as the values for my specific problem are as ...
1
vote
2answers
33 views

An exercise in number theory: associates elements

I have a question for you about associates elements in an integral domain. Let $R$ be an integral domain and define $aR := \{ ar \; | \; r \in R\}$. In the following, for $unity$ (denoted with $u$) I ...
2
votes
1answer
49 views

For which integer n, sin(π/n) can be a rational?

When I was studying about the trigonometric functions, I sow that most of the values of sin(π/n) and cos(π/n) n∈N are irrational. How can we determine all the n∈N such that sin(π/n) or cos(π/n) is a ...
3
votes
2answers
51 views

Sum of square roots of integers

Let $x, y$ be integers and consider the equation $$\sqrt{x}+\sqrt{y}= 8 \sqrt{31}.$$ It is claimed that this implies $\sqrt{x}= a\sqrt{31}$ and $\sqrt{y}=b \sqrt{31}$ for $a,b$ integers. While this ...
2
votes
3answers
32 views

Number system, divisibility

For how many values of $n$, where $n<55$, is the expression $(n)(n+1)(2n+1)/6$ divisible by $4$? I checked $n$ and $n+1$ separately for divisibility by $4$. My ans came out to be $26$. But the ...
2
votes
3answers
93 views

Find $x > 0$ for which $\int_{0}^{x} [t]^2 \ dt = 2 (x-1)$.

What are all possible $x > 0$ for which the following equation is satisfied? $$\int_{0}^{x} [t]^2 \ dt = 2 (x-1),$$ where $[.]$ denotes the bracket (or floor) function. I guess we will have to ...
1
vote
1answer
46 views

Question in elementary number theory

I have a question. Suppose that $a$ and $b$ are two natural numbers so that $ a<b$ and $ a\nmid b$. Put $ d=ka$, where $ k\not=0,1,t\dfrac{b}{\gcd(a,b)}$, for $ t\geq 1$. I want to prove that $ ...
0
votes
0answers
29 views

Differential Diophantine Equations?

So this is both a question on its own as well as a request for where I can find information on a given topic. Consider Differential Equations in two variables of the form: $$P(Z,Z', Z'' ... Z^{[n]}, ...
11
votes
1answer
175 views

Is the equation $\phi(\pi(\phi^\pi)) = 1$ true? And if so, how?

$\phi(\pi(\phi^\pi)) = 1$ I saw it on an expired flier for a lecture at the university. I don't know what $\phi$ is, so I tried asking Wolfram Alpha to solve $x \pi x^\pi = 1$ and it gave me a bunch ...
2
votes
1answer
31 views

The number of distinct multiples of composites greater than $n$ that can be factored into two naturals less than or equal to $n$

Given a list of composites between $n$ and $\lfloor \frac{n^2}{2} \rfloor$: What would be the most efficient way to count, for each composite, the number of its distinct multiples that can be ...
5
votes
1answer
81 views

Irrational to power of itself is natural

I've been thinking about a natural number like $n$ so that $x^x=n$ for some irrational $x$ but i couldn't find anything. As i didn't know how to approach the problem at all, i tried to make some ...
2
votes
0answers
48 views

Prove $a^m\equiv a^{m-\phi(m)}\pmod m$ for all positive integers

Prove that if $a,m$ are positive integers, then $$a^m\equiv a^{m-\phi(m)}\pmod m.\tag 1$$ If gcd$(a,m)=1$ then this is Euler's theorem. Denote gcd$(a,m)=k$ and $a=xk,m=yk$ then we need to prove ...
0
votes
1answer
35 views

Sophie Germain primes

Why did Germain come up with her Germain primes? I am intrigued to know why Sophie came across these primes. Do they have any applications?
3
votes
2answers
48 views

Totient Function $\varphi{(x)}=24$

I'm trying to solve for all $x$. I'm thinking I'd like to take advantage of the fact that $\varphi$ is multiplicative if the factors of a number are coprime. So let $x=ab, (a,b)=1$. This is not the ...
-1
votes
3answers
111 views

find the remainder when $19^{22}$ is divided by $92$.

find the remainder when $19^{22}$ is divided by $92$. Will Euler's totient function help us?
2
votes
1answer
33 views

is my induction proof sufficient?

question; prove that $\forall\ n\ge4, n\in \mathbb{Z}, \ n!\gt n^2$. my work; let $n=4$ then $4!=24 \gt 4^2=16.$ true. now assume $n! \gt n^2$ is true for all $n\le k$ so now assume $k! \gt ...
0
votes
0answers
21 views

How to find a certain uppper bound (see details)?

What would be the most efficient way to find this upper bound? Given natural number n and a natural number d < n, find the ...
2
votes
2answers
40 views

Dividing by x on two sides of an equation is not always the same equation??

$y = p*x$ $\frac{y}{x} = \frac{p*x}{x}$ These equations are 'equal' via common math principles. If $x = 0$, then in the first equation $y = 0$. In the second equation, its not defined (since you ...
0
votes
0answers
19 views

On problem on two equations

Let $n_{1}$ and $n_{2}$ are natutal number such that $m_{11}, m_{12}\in\{0,1...,2^{n_{1}}-1\}$ and $m_{21}, m_{22}\in\{0,1...,2^{n_{2}}-1\}$. Also $m_{11}$ and $m_{22}$ are odd. Now we have equations: ...
0
votes
1answer
81 views

Without using group theory, How to Prove $n|\phi(a^n-1)$, where $\phi$ is Euler's Totient function. [closed]

Let $\phi$ be Euler's Totient funcion, how to prove this property? If possible can we have an elementary proof without leveraging the group theory? $$n|\phi(a^n-1), \forall n,a>1, \gcd(a,n)=1$$ ...
2
votes
3answers
38 views

Chinese Remainder Theorem problem error

I am trying to find all integers that give remainders 1,2,3 when divided by 3,4,5 respectively. So I start defining $$a_1=1, a_2=2, a_3=3,$$$$ m_1=3, m_2=4, m_3=5,$$$$ m_1m_2=12, m_1m_3=15, ...
0
votes
0answers
27 views

Mathematical Modeling for the Mapping Relationship

I have encountered a problem in my research and have no idea how to model the problem. To simplify the description, I tell a game with the same rule instead of the original problem. Consider two set ...
3
votes
6answers
910 views

Among any three consecutive positive integers one is a multiple of 3

If $8q,8q+1,8q+2$ are consecutive positive integers, then prove that at least one among them is a multiple of $3$. One proof is that by expressing $8q=3m+r$. Is there any other way of doing it ...
3
votes
3answers
121 views

Divisibility of consecutive numbers by 6

Prove that the product of three consecutive positive integers is divisible by 6 by expressing the positive integer n as n=8*q+r I expressed the problem as n(n+1)(n+2) where n is a positive integer I ...
2
votes
1answer
48 views

suppose a>1 is an integer, and p is an odd prime number.

Suppose $a>1$ is an integer, and $p$ is an odd prime number. Prove that each odd prime factor of $(a^p)-1$ which does not divide $a-1$ should be in the form $2pt+1$. My Approaching: ($a^p)-1$ is ...
3
votes
5answers
578 views

The sum of three consecutive cubes numbers produces 9 multiple

I want to prove that $n^3 + (n+1)^3 + (n+2)^3$ is always a $9$ multiple I used induction by the way. I reach this equation: $(n+1)^3 + (n+2)^3 + (n+3)^3$ But is a lot of time to calculate each ...
4
votes
3answers
100 views

Elementary, direct proof of when $5$ is a quadratic residue mod $p$

$\newcommand{\kron}[2]{\left( \frac{#1}{#2} \right)}$ It's easy to use Quadratic Reciprocity to show that $\kron{5}{p} = \kron{p}{5} = 1$ when $p \equiv \pm 1 \pmod 5$, and is $-1$ when $p \equiv \pm ...
0
votes
1answer
151 views

Find sum of all permutations

We call two arrays A and B with length n almost equal if for every i (1 <= i <= n) ...
1
vote
1answer
48 views

Solving Equations in $\mathbf{Z}/n\mathbf{Z}$ with Indices

Consider the equation $x^4 = 7,$ which we wish to solve in $\mathbf{Z}/29\mathbf{Z}.$ I was taught a technique for solving this problem, but I can't understand it. I'll try my best to describe it, ...