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

learn more… | top users | synonyms

7
votes
4answers
272 views

The largest integer less than $n$ is $n-1$

Let $n$ be a positive integer. Prove that the largest integer which is less than $n$ is $n-1$. Attempt of a solution: Since $n$ is a positive integer $n>0$. I think I have to use the well-ordering ...
0
votes
1answer
40 views

Having trouble with Chinese Remainder Theorem

I am having trouble with the Chinese Remainder Theorem. For this question..the equation $5x\equiv 3 \pmod6$ I found there is exactly one incongruent solution modulo $6$. But then I found 3 solutions ...
0
votes
1answer
15 views

Geometric representation for pentahedral numbers?

Triangular numbers are the sum of the integers up to n. Tetrahedral numbers are very similar, and can be shown to represent the number of balls stacked in a pyramid shape. Is there a name given to ...
2
votes
1answer
66 views

Prime factorization problem…

Here's the entire problem: By considering the prime decomposition of $gcd( ab, n )$, show that if $a , b ,n$ are integers with $n$ relatively prime to both $a,b$ , then $n$ is relatively prime to ...
3
votes
3answers
65 views

Best resource to learn quadratic reciprocity?

I took a very basic intro to number theory course last semester. We learned about many of the standard topics (gcd, primes, cryptography, congrences, pythagorean triples, etc), but we never learned ...
0
votes
1answer
185 views

Why elements of the set can be Goldbach pairs for a given even number?

Let's take even number $100$ as an example (an example in the paper): Fom $2$ to $\sqrt{100}$ there's four primes:$\ 2,\ 3,\ 5,\ 7.\ $Let $$ \begin{align*} &A=\{n: n \in \mathbb{Z^+}, ...
2
votes
1answer
43 views

Find the smallest number

Given n numbers we need to find(if possible) the least number k in the range [a,b] such that each number is either divisible by k or divides k. Can we find such number k ? Example: let n=4 and ...
3
votes
2answers
111 views

$n^2-79n+1601$ always a prime?

I am struggling with proving or disproving this: $n^2-79n+1601$ is a prime for all natural numbers $n$ (except multiples of $1601$). This somehow has a relation to Stanislaw Ulam spiral. What ...
1
vote
2answers
174 views

Jugs of water puzzle…

The problem: Explain how to measure 8 units of water using only two jugs, one of which holds precisely 12 units, the other holding precisely 17 units of water. Given the hint "Find ...
3
votes
1answer
47 views

squares that can be divided to two squares

There are some squares like 169 that can be divided into two squares(16 and 9). I classify them into two groups: A:squares that their rightmost number isn't 0(like 169 and 4225) B:squares that their ...
1
vote
1answer
38 views

Composite numbers and perfect squares

Suppose $a$ is a positive integer $(2a+1)$ and $(3a+1)$ are perfect squares. Prove that $(5a+3)$ is a composite number. I really do not know the relationship between perfect squares and composite ...
1
vote
2answers
31 views

Rational Number of a given fraction

Find all rational numbers $\frac pq$ such that $\frac pq=\frac {p^2 +30}{q^2 +30}$. How can I go about it. If I substitute p and q by real values $\frac pq$ gets innumerable rational numbers
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
109 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
117 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
48 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
50 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
36 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
68 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
54 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
94 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
49 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 ...