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

learn more… | top users | synonyms (1)

1
vote
2answers
74 views

Proving divisibility of numbers

Let us take a two digit number and add it to its reverse.We have to prove that it is divisible by 11. Same way,if we subtract the larger number from the other,it is divisible by 9.How can we explain ...
1
vote
1answer
72 views

Can anybody validate this WolframAlpha computation?

Can anybody validate this WolframAlpha computation? http://www.wolframalpha.com/input/?i=GCD%5BDivisorSigma%5B1%2Cx%5D%2C+DivisorSigma%5B1%2Cx%5E2%5D%5D Thank you!
4
votes
4answers
3k views

Solve Modular Equation

Here is an modular equation $$5x \equiv 6 \bmod 4$$ And I can solve it, $x = 2$. But what if each side of the above equation times 8, which looks like this $$40x \equiv 48 \bmod 4$$ Apparently ...
1
vote
0answers
87 views

Operations between temporal discrete intervals

I am going to present you my problem and ask you for solutions' references. I have a discrete temporal series, which is the sequence of Natural numbers $T = \lbrace 1, 2, \dots, N \rbrace$. An Event ...
0
votes
1answer
172 views

Space complexity of the segmented sieve of Eratosthenes

It's commonplace to say that without compromising on the time complexity of $O(n\log\log n)$, the space complexity of the sieve of Eratosthenes can be reduced to $O(\sqrt{N})$ using a segmented ...
0
votes
1answer
50 views

Typo in Crandall and Pomerance pp. 121

In Crandall and Pomerance "Prime Numbers: A Computational Perspective" Second Ed., pp. 121 just before Eq. (3.1) it says: "The number of steps in the sieve of Eratosthenes is proportional to ...
4
votes
4answers
445 views

Find a function that gives this sequence: $+1,+1,-1,+1,+1,-1,-1,+1,+1,+1,-1,-1,+1,-1,-1,…$

I start with a string $S_1=1$ then the $(n+1)$-th string is $S_{n+1}=\{ S_n,+1 ,-(S_n)\}$ if $S_j=\{s_1,s_2,s_3,..., s_i\}$ then $-(S_j)$ is defined as $-(S_j)=\{-(s_i), -(s_{i-1}),..., -(s_3), ...
3
votes
1answer
197 views

Proving equivalences between prime counting functions.

If we have that: $$\theta(x)=\sum_{p\leq x}\log p,$$ and $$\psi(x)=\sum_{n\leq x}\Lambda(n)$$ Where $\Lambda(n)=\log p $ if $n=p^m$ and $\Lambda(n)=0$ in another case. How can I prove that : 1) ...
4
votes
4answers
166 views

Given $a>b>2$ both positive integers, which of $a^b$ and $b^a$ is larger?

Given $a>b>2$ both positive integers, which of $a^b$ and $b^a$ is larger? I tried an induction approach. First I showed that if $b=3$ then any $a \geq4$ satisfied $a^b<b^a$. Then using that ...
6
votes
2answers
435 views

Simple number theory problem

I found this question in a textbook on number theory: For which integer c will $\;\displaystyle{\frac{c^6 - 3}{c^2 + 2}}\;$ also be an integer? I wonder if there is a solution which is not based ...
6
votes
2answers
505 views

Convergence/Divergence of a particular infinite nested radical

Is it known if the following infinite nested radical converges or diverges (for $n \in \mathbb N$)?: $$R(n) = \sqrt{n+\sqrt{(n+1)+\sqrt{(n+2)+ \cdots}}}$$ I recently became interested in these ...
0
votes
3answers
102 views

How can I find the smallest possible of full miles to get full kilometers?

$1 \textrm{mile} = 1.609344 \textrm{km}$ I know that using $1000000$ miles I can move the decimal point and get a full number of $1609344 $km. But how can I find the smallest amount of full miles ...
1
vote
3answers
765 views

Prime generating functions

I'm studying prime numbers at school and I've seen some functions that generate mostly prime numbers. I'm talking about : $$\text{Euler's polynomial : } n^2+n+41$$ $$\text{Legendre's polynomial : } ...
0
votes
3answers
63 views

MODULAR problem

What will be the remainder when 64! is divided by 71? Do we need to solve this problem by using MOD theorem or need to expands the factorial?
0
votes
2answers
702 views

Missing Exercises in Elementary Number Theory by Underwood Dudley.

I'm a beginner in math and I just started studying Elementary Number Theory by Dudley. So far I'm impressed, but I've noticed that the book does not include all the solutions to the exercises they ...
7
votes
4answers
252 views

Integrality of $\frac{n}{3} + \frac{n^2}{2} + \frac{n^3}{6}$

I've been asked to provide a proof for If $n$ is an integer then $$\frac{n}{3} + \frac{n^2}{2} + \frac{n^3}{6}$$ is also an integer. Any help would be appreciated
2
votes
2answers
53 views

Modular Arithmetic & Congruences

Show that if $p$ is an odd prime and $a \in \mathbb Z$ such that $p$ doesn't divide $a$ then $x^2\equiv a(mod p)$ has no solutions or exactly 2 incongruent solutions. The only theorem that I ...
6
votes
4answers
153 views

Determine if the expression is an integer.

I'm tryin to solve this: Determine $k$ such that $\frac{k^2-87}{3k+117}$ is an integer. I think chinese remainder theorem will be useful, but i don't see how.
3
votes
3answers
76 views

prove that the order of $2$ mod p is $2^{n+1}$

I'm trying to prove this: Let $p$ be a prime factor of $F_n=2^{2^n}+1$, prove that order of $2$ mod p is $2^{n+1}$. I know that $2^{2^{n+1}} \equiv 1 \mod p$. But it only means that $ord(2)_p$ its a ...
3
votes
1answer
122 views

Odd part of $n-1$ and primes

Using $n=11$ as an example: ...
3
votes
0answers
130 views

Decimal representation and Peano axioms

I really tried to find similar questions but didn't manage to find them. Please, forgive me if this question is a duplicate. I also apologize for my English. So. The question. We're given five Peano ...
2
votes
1answer
149 views

Foul play in Pell’s equation

Pells equation $x^2-dy^2=1$ has the obvious x and y solutions $x=n$, $y=1$ for $d=n^2-1$. The next and higher solution for the same d is $x=2n^2-1$ and $y=2n$. This offers a method for calculation ...
2
votes
1answer
350 views

Any formula to find the maximum $n$th power of $x$ contained in a number?

Is there any formula to find the maximum $n$th power of $x$ contained in a number? Say I need to find $n$ where $x$ is $2$ and the number is $25$. So the answer must be $4$. The problem statement ...
0
votes
2answers
111 views

Definition of period of a decimal representation of a number

I need to define the period of a decimal representation of a number!! Thanks in advance!!
1
vote
2answers
150 views

Is there a formula in permutations and combinations if we are to find the sum of number of 1's in binary expansion of a number from 1 to n

We are given $N$. Suppose $f(x) =$ number of $1$'s in the binary expansion of $x$. We have to calculate $f(1) +f(2) +f(3)+ \dots +f(N)$. So is there a formula for this sum directly in terms of ...
0
votes
1answer
47 views

Question involving Legendre symbols

Let r,p,q be distinct odd primes. Let 4r divide p-q. Show that (r/p) = (r/q) Where (a/b) is the Legendre symbol. I'm sure we are suppose to use the law of quadratic reciprocity. I don't think this ...
1
vote
2answers
58 views

How to prove $x^{2}+x=1$ has a solution in $\mathbb{Z}_{p}$ if and only if $p=5$ or $p\equiv \pm1\bmod 5$

What is the proof of the theorem which says: there is a root of the equation $x^{2}+x=1$ in $\mathbb{Z}_{p}$ if and only if $p=5$ or $p\equiv -1\bmod 5$ or $p\equiv 1\bmod 5$.
6
votes
1answer
182 views

Combinatorial proof of the fact $p$ doesn't divide $ n \choose p^k$

Let $p^k | n$ and $p^{k+1} \nmid n$. Is there any combinatorial proof of the fact that $p \nmid {n \choose p^{k}} $ ?
6
votes
2answers
161 views

Find all positive integers $x$ such that $13 \mid (x^2 + 1)$

I was able to solve this by hand to get $x = 5$ and $x =8$. I didn't know if there were more solutions, so I just verified it by WolframAlpha. I set up the congruence relation $x^2 \equiv -1 \mod13$ ...
3
votes
1answer
102 views

Is partition function increasing function?

I have some exercises which require knowing the number of partitions of particular numbers, so I used some python code which I found on internet to compute the values of the partition function for the ...
4
votes
2answers
104 views

Proving divisibility in elementary number theory problem

Find all positive integers n such that $(n+1)\mid(n^2+1)$. What I have done so far. I noticed that $ n^2 + 1 = (n + 1 - 1)^2 + 1 = (n + 1)^2 -2(n + 1) + 2$. Hence, for the relation to be true, we ...
11
votes
3answers
371 views

Irrationality of $\sqrt 2$ using induction

I came upon this exercise in a textbook. I know that $\frac{n}{b} \ne \sqrt{2} $ for all $b \gt 0$ and $n \le N_0$. How can I then show that $\frac{N_0 + 1}{b} \ne \sqrt{2}$ for all $b \gt 0$?
3
votes
5answers
194 views

How to (quickly) prove that $24p+17$ is not a square number

Computer says $24p+17$ is not square number for $p<10^7$ so I guess it's not. I know that squares of odd numbers are all $8p+1$ but $24p+17$ passes the test And how to solve problems like this in ...
0
votes
2answers
179 views

If $a \mid c, b \mid c, \gcd (a,b)=1$ then $ab \mid c.$ [duplicate]

If $a \mid c, b \mid c, \gcd (a,b)=1$ then $ab \mid c.$ I understand that given problem is true. however im struggling with writing to prove. I let A=2 , B= 3 , C= 6 2 l 6= 3 3 I 6=2 3*2 l 6=1 ...
0
votes
1answer
200 views

Minimum number of moves to equalize a list

Given a list of $n$ integers. In one move we can either decrease exactly one element by $1,2$ or $5$. What is the minimum number of moves required to equalize the list? For example: If the list is ...
1
vote
2answers
2k views

Counting squares of maximum size in a rectangle

Given a rectangle of sides $m$ and $n$. $( m,n \in [1,1000] )$ We can cut the rectangle into smaller identical pieces such that each piece is a square having maximum possible side length with ...
2
votes
0answers
103 views

In $ℤ/Nℤ$, which units are successors to zero divisors?

What are the units $x$ in $ℤ/Nℤ$ of the form $x = 1 + \overline{kd}$ for a divisor $d$ of $N$ and $k ∈ ℤ$, i.e. $$U_N[d] := \{x ∈ (ℤ/Nℤ)^×;\; ∃ k ∈ ℤ : x = 1 + \overline{kd}\} = \ker \big((ℤ/Nℤ)^× → ...
1
vote
3answers
61 views

Conjecture on combinate of positive integers in terms of primes

Along a heuristic calculation, I am struggeling with a possible proof for my following conjecture: Every positive integer $n\in \Bbb N$ can be written as a unique combination of $a,b \in \Bbb N$, ...
2
votes
1answer
62 views

Find all functions $f$ so that $d(f(x))=x$ for every natural $x$.

Help me find all functions $f(x)$, $f:\mathbb N \to \mathbb N$, so that $d(f(x))=x$ for every natural number $x$ where $d(x)$ is number of divisors of $x$. My works until now: Clearly $f(1)=1$. We ...
0
votes
2answers
51 views

Solving A Linear Congruential System

I need to find a prime p which makes: $p\equiv {\pm1}\text{ (mod }8)$ and $p\equiv {\pm1}\text{ (mod }12)$ How could I find such $p$? Is there any specified method I can use? I'd be grateful if ...
1
vote
2answers
4k views

If $\gcd(a,b)=1$ and $a$ and $b$ divide $c$, then so does $ab$

Using divisibility theorems, prove that if $\gcd(a,b)=1$ and $a|c$ and $b|c$, then $ab|c$. This is pretty clear by UPF, but I'm having some trouble proving it using divisibility theorems. I was ...
1
vote
6answers
221 views

Solving a Linear Congruence

I've been trying to solve the following linear congruence with not much success: 19 congruent to $19\equiv 21x\text{ (mod }26)$ If anyone could point me to the solution i'd be grateful, thanks in ...
15
votes
6answers
384 views

If $(a,b,c)=1$, is there $n\in \mathbb Z$ such that $(a,b+nc)=1$?

In the book Lectures on modular forms, one finds the statement at page 8 that If $(a,b,c)=1$ then there is $n\in \mathbb Z$ such that $(a,b+nc)=1$. I know that, if $(a,b)=1$, then we can ...
15
votes
4answers
545 views

Need help understanding Erdős' proof about divergence of $\sum\frac1p$

I'm looking at proofs from Proofs from the Book (Martin Aigner, Günter M. Ziegler). The proof I'm having trouble is the sixth proof of the infinitude of the primes they give (on page 5; although I'll ...
3
votes
5answers
133 views

For any integer $a$, there is an integer $k$ such that $a^2=3k$ or $a^2=3k+1$

Let $a$ be an integer. Prove that there exists an integer $k$ such that $a^2=3k$ or $a^2=3k+1$. Here is what I did: I said: $a\in\{\ldots,-3,-2,-1,0,1,2,3,\ldots\}$. When I put 2 into $a^2$, I ...
4
votes
2answers
87 views

Choosing $a$ s.t. $\frac{a^k - 1}{a-1}$ is not a prime power

Let us suppose that we are presented with a positive integer $k$ and asked to come up with a positive integer $a$ such that $\frac{a^k - 1}{a-1}$ is not a prime power, or just to prove in an ...
5
votes
5answers
142 views

Simplifying $a(a-2) = b(b+2)$

I reduced a number theory problem to finding all ordered pairs $(a,b)$ that satisfy the equation $a(a-2) = b(b+2)$ in a certain range. After thinking about this for a while, I figured that either $a = ...
4
votes
1answer
182 views

Legendre Symbol - Find Prime $p$ Which Divides A Polynomial

I need to find a general form of a prime number $p$ which divides the polynomial $x^2-6$, i.e. $p$ such that $x^2 - 6\equiv 0\text{ (mod }p)$. By Legendre symbol, I actually need to find a prime p ...
1
vote
2answers
89 views

Find the greatest integer $N$ such that…

Find the greatest integer $N$ such that $N<\dfrac{1}{\sqrt{33+\sqrt{128}}+\sqrt{2}-8}$. The way I did it is this: first, I rewrote the biggest square root as $\sqrt{1+2*16+8\sqrt{2}}$. Then I ...
2
votes
1answer
122 views

Let $p$, $q$ be primes such that $q \equiv 2 \pmod{5}$ and $p = 4q+1$. Show that $100^{q} \not\equiv 1\pmod{p} $.

Let $p$, $q$ be two primes such that $q \equiv 2 \pmod{5}$ and $p = 4q+1$. Show that $$100^{q} \not\equiv 1\pmod{p} $$ Here is one way that I tried to tackle this (and failed, obviously...): ...