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

learn more… | top users | synonyms

8
votes
5answers
495 views

Questions about composite numbers

Consider the following problem: Prove or disprove that if $n\in \mathbb{N}$, then $n$ is prime iff $$(n-1)!+n$$ is prime. If $n$ is composite and greater than $1$, then $n$ have a divisor less than ...
6
votes
4answers
263 views

A “fast” way for finding sum of the numbers from $1$ to $100$,which are not divisible by $3$ and $5$

Find sum of numbers from $1$ to $100$ which are not divisible by $3$ and $5$? I can understand that the here we require to sum up these numbers: ...
0
votes
2answers
90 views

Finding all positive values of y and z for $6y + 5z = 960$?

How do I solve $6y + 5z = 960$ for $0 < y < z$ using the Extended Algorithm?
15
votes
5answers
1k views

How do we prove $n^n \mid m^m \Rightarrow n \mid m$?

I'm not sure I've got this right. When proving $a^n \mid b^n \Rightarrow a \mid b$, can we do this indirectly? In short, "Suppose $a$ does not divide $b$, this implies that $a^n$ does not divide ...
1
vote
2answers
87 views

General approach for problem for finding sum from $1$ to $N$ when all $a$'s are replaced by $b$'s

The problem is: Find the sum of all the numbers from $1$ to $100$ when all the $6$'s are replaced by $9$'s. I need some ideas on how to approach this kind of problems? Please explain your ideas, ...
5
votes
5answers
534 views

Proving two gcd's equal

I'm having problems with an exercise from Apostol's Introduction to Analytic Number Theory. Given $x$ and $y$, let $m=ax+by$, $n=cx+dy$, where $ad-bc= \pm 1$. Prove that $(m,n)=(x,y)$. I've ...
3
votes
2answers
497 views

Base system and divisibility

I have seen the following one. Please give the proof of the observation. We know that, The difference between the sum of the odd numbered digits (1st, 3rd, 5th...) and the sum of the even numbered ...
1
vote
1answer
82 views

If $abc\equiv x\pmod{p}$ and $x\not\equiv 0\pmod{p}$ what are the number of solutions for given $x$ and $p$ [duplicate]

Possible Duplicate: Solutions of $\prod_{i=1}^n x_i = c$ mod p I guess it should be $3(p-2)+1$ modulo $n$ as there are $3$ possibilities for abc to be congruent to $2,\cdots ,p-1$ each and ...
6
votes
1answer
792 views

Relation between different ways of accessing bernoulli numbers with matrices

First Variant: Bernoulli numbers can easily be expressed by linear algebra equations. For example just using the recursion formula $$\sum_{k=0}^{n-1}{n\choose k}B_k=0$$ which is equation (34) from ...
2
votes
3answers
196 views

Divisors of all values of polynomial over $\Bbb Z\,$ (fixed divisors)

From Fundamentals of Number Theory by LeVeque, section 3.1, prob. 1 Let $f(x) = a_0x^n + \cdots + a_n$ be a polynomial over Z. Show that if $r$ consecutive values of $f$ (i.e., values for consecutive ...
2
votes
2answers
444 views

The number is a perfect square if and only if $k=n$

Let $k$ and $n$ be positive integers. Show that $$(k+1)^2k^2(n+1)^4-2k(k+1)n(n+1)^2(2kn+k+1)+n^2(k+1)^2$$ is a perfect square if and only if $k=n$.
0
votes
2answers
152 views

Where is the mistake in this reasoning?

If we make a table such that each column contains numbers modulo $m$ and each row containing numbers modulo $n$. Let us denote the element $a_{ij}=x$ and $a_{i'j'}=y$ Where $0\leq ...
5
votes
2answers
199 views

Finding the largest set of integers over an interval where the sum of any 'k' elements is unique

Consider the set $(s_1, ..., s_N) \in S$, where all $s_i$ are positive integers selected from some interval $[M, L]$ and the sum of any $k$ integers in $S$ is required to be unique and to have a ...
16
votes
7answers
3k views

Prime dividing the binomial coefficients

It is quite easy to show that for every prime $p$ and $0<i<p$ we have that $p$ divides the binomial coefficient $\large p\choose i$; one simply notes that in $\large \frac{p!}{i!(p-i)!}$ the ...
2
votes
2answers
256 views

Testing pythagorean triples: $333,444,555$

In this page there is a necessary and sufficient test given for testing Pythagorean triples: A simpler, more powerful test is, (by naming the even leg a): $(c − a)$ and $\large\frac{(c − b)}{2}$ ...
2
votes
3answers
133 views

How to find the least $N$ such that $N \equiv 7 \mod 180$ or $N \equiv 7 \mod 144$ but $N \equiv 1 \mod 7$?

How to approach this problem: N is the least number such that $N \equiv 7 \mod 180$ or $N \equiv 7 \mod 144$ but $N \equiv 1 \mod 7$.Then which of the these is true: $0 \lt N \lt 1000$ $1000 ...
5
votes
1answer
286 views

Proof of $p \mid m^p-m$ for prime $p$

This problem is well-known, but my proof is different from the one I found, so just decided to put it here in case someone finds a mistake. So I want to prove $p \mid m^p-m$, where $p$ is a prime ...
-3
votes
2answers
256 views

this is a question from number theory

I want to know what happens when $M$ to the power $N$ is divided by $K$, where $M$, $N$, and $K$ are natural numbers.
0
votes
1answer
242 views

Number of divisors excluding set of primes S

Quite much time ago I found task where I was pleased to compute number of divisors (they are primes!) excluding numbers from set S (in other words, set S should only contain divisors of number N, ...
12
votes
1answer
2k views

Proof of Euler's Theorem without abstract algebra?

Every proof I've seen of Euler's Theorem (that $\gcd(a,m) = 1 \implies a^{\phi(m)} \equiv 1 \pmod m$) involves the fact that the units of $\mathbb{Z}/m\mathbb{Z}$ form a group of order $\phi(m)$. ...
5
votes
3answers
724 views

Questions on perfect squares

I recently attended a test which ask me two question based on perfect squares; here they are: $1.$ How many even perfect squares between $1000$ and $5000$ are divisible by both $5$ and $9$? $2.$ Can ...
3
votes
2answers
8k views

Sum of n consecutive numbers [duplicate]

Possible Duplicate: Proof for formula for sum of sequence $1+2+3+\ldots+n$? Is there a shortcut method to working out the sum of n consecutive positive integers? Firstly, starting at $1 ...
4
votes
3answers
211 views

How to solve this very quickly?

A number leaves a remainder $2$ when divided by $9$.Which of the following could not be the remainder when it is divided by $45$? $20$ $30$ $29$ $38$ How could we solve this under a ...
1
vote
1answer
312 views

Find number of interesting numbers (China TST 2011)

A positive integer $n$ is known as an interesting number if $n$ satisfies $$ \left\{\frac{n}{10^k}\right\} > \frac{n}{10^{10}} $$ for all $k=1, 2, \ldots, 9$, where $\{x\}=x - \lfloor x \rfloor$. ...
9
votes
2answers
587 views

Value of cyclotomic polynomial evaluated at 1

Let $\Phi_n(x)$ be the usual cyclotomic polynomial (minimal polynomial over the rationals for a primitive nth root of unity). There are many well-known properties, such as $x^n-1 = ...
7
votes
4answers
338 views

A “fast” way to manually compute $3^{41}+7^{41} \pmod{13}$

The problem: Find the remainder of $3^{41}+7^{41}$ when divided by $13$. My approach is by utilizing the cyclicity of remainders for examples $3^1,3^2,3^3,3^4,3^5 \text{ and }3^6$ when divided ...
4
votes
3answers
224 views

How to find maximum $x$ that $k^x$ divides $n!$

Given numbers $k$ and $n$ how can I find the maximum $x$ where: $n! \equiv\ 0 \pmod{k^x}$? I tried to compute $n!$ and then make binary search over some range $[0,1000]$ for example compute ...
32
votes
7answers
1k views

Bad Fraction Reduction That Actually Works

$$\frac{16}{64}=\frac{1\rlap{/}6}{\rlap{/}64}=\frac{1}{4}$$ This is certainly not a correct technique for reducing fractions to lowest terms, but it happens to work in this case, and I believe there ...
3
votes
5answers
187 views

Interesting question about twin cousins

If $p$ and $p + 2$ are (twin) primes, then $p + (p + 2)$ is divisible by $12$, where $p > 3$.
7
votes
3answers
899 views

How to determine number with same amount of odd and even divisors

With given number N, how to determine first number after N with same amount of odd and even divisors? For example if we have N=1, then next number we are searching for is : ...
8
votes
3answers
388 views

How are the integral parts of $(9 + 4\sqrt{5})^n$ and $(9 − 4\sqrt{5})^n$ related to the parity of $n$?

I am stuck on this question, The integral parts of $(9 + 4\sqrt{5})^n$ and $(9 − 4\sqrt{5})^n$ are: even and zero if $n$ is even; odd and zero if $n$ is even; even and one if $n$ is ...
4
votes
1answer
126 views

Pairwise prime triples of integers satisfying $x^2+y^2=z^2$

The following property has been stated without proof in a problem solving book (not as a problem, hence no solution). I also looked at the number theory text I have, and I cannot find it. All ...
23
votes
4answers
542 views

Elementary proof of $m^n\neq n^m$ for almost all natural numbers $m\neq n$

$2^4=16=4^2$. In fact, $\{2,4\}$ is the only pair of natural numbers with that property, i.e. if $m<n$ are natural numbers and $m^n=n^m$, then $m=2$ and $n=4$. This is easily seen with some ...
8
votes
4answers
316 views

question about division

The question is from the following two problems: Let $x$ and $y$ be positive integers such that $3x+7y$ is divisible by $11$. Which of the following must also be divisible by $11$? A. $4x+6y$ ...
15
votes
2answers
743 views

Puzzle: $(\Box @)+(\Box @) = (\Box\bigstar\Box$)

Some ETs follow a positional number system, with the same base as the number of fingers on their hand. The following inscription is all the evidence we have: $$(\Box @)+(\Box @) = \Box\bigstar\Box ...
4
votes
12answers
1k views

Prove that $6|2n^3+3n^2+n$

My attempt at it: $\displaystyle 2n^3+3n^2+n= n(n+1)(2n+1) = 6\sum_nn^2$ This however reduces to proving the summation result by induction, which I am trying to avoid as it provides little insight.
1
vote
2answers
195 views

First problems from text on number theory

Express $635,318,657$ as sum of two fourth powers in two different ways. It is the smallest number with this property? and $1105$ can be expressed as the sum of two squares in 4 different ...
11
votes
6answers
2k views

Prime factorization of 1

Fundamental Theorem of Arithmetic says every positive number has a unique prime factorisation. Question: If 1 is neither prime nor composite, then how does it fit into this theorem?
1
vote
3answers
92 views

Common denominators

Is there a function to get all common denominators (except for 1) for two numbers? I think it could use summation, the lower limit would be 1 and upper limit would be the greatest common denominator, ...
9
votes
2answers
579 views

Doubt in finding number of non-prime factors of an integer

The question is: Find the number of non-prime factors of $4^{10} \times 7^3 \times 5^9$. I represented the number as $2^{20} \times 7^3 \times 5^9$ then the number of factors of this integer ...
0
votes
4answers
314 views

Finding the last two digits of the expansion of $2^{12n}-6^{4n}$

The question is: Find the last two digits of the expansion of $2^{12n}-6^{4n}$ where $n$ is any positive integer. If we put the value of $n=1$ we would get $2800$. For $n = 2$ the result will ...
2
votes
1answer
165 views

Question regarding expansion in base $b$ proof

In the textbook "Elementary Number Theory" by Kenneth H. Rosen, Theorem 12.3. (page 472) The real number $\alpha$, $0 \leq \alpha \lt 1$, has a terminating base $b$ expansion if and only if ...
0
votes
2answers
160 views

Understanding of the proof of “$d$ solutions for $kx \equiv l \pmod{m}$”

The question is from the proof of a theorem in Hardy's An Introduction to the Theory of Numbers. THEOREM 57. If $(k, m) = d$, then the congruence $$(5.4.1)\qquad kx \equiv l \pmod{m}$$ is ...
2
votes
1answer
70 views

How to build up the congruence equation?

The following is from Hardy's An Introduction to the Theory of Numbers: A lecture is given on every alternate day (including Sundays), and that the first lecture occurs on a Monday. When will a ...
2
votes
1answer
164 views

Non-negative solutions of the equation $5^n+7^m=k^3$

How can I find all triples $(m,n,k)$ of non-negative integers such that $5^n+7^m=k^3$?
10
votes
4answers
411 views

Why is “working in $\mathbb {Z}_m$” essentially the same as “working with congruences modulo m”?

Due to my ignorance, I only superficially know the definition of congruence in number theory: For a given positive integer $n$, two integers $a$ and $b$ are called congruent modulo $n$, written ...
0
votes
1answer
396 views

Solving $x^{12}-x^{10}=2$ in ${\Bbb Z}_{11}$

The question is from a multiple choice problem: How many elements $x$ in the field ${\Bbb Z}_{11}$ satisfy the equation $x^{12}-x^{10}=2$? A.1 B.2 C.3 D.4 E.5 I know that one may need Fermat's ...
4
votes
1answer
227 views

Why is $a\equiv b \pmod n$ equivalent to the congruences $a\equiv b,b+n,b+2n,\dots,b+(c-1)n\pmod {cn}$?

I learned the following proposition (in which there is no proof) in a GRE math preparation book. I don't understand what it means and I am not able to find any theorem about this statement in Hardy's ...
0
votes
1answer
262 views

Sum of two squares [duplicate]

Possible Duplicate: Prove that $n$ is a sum of two squares? I was reading this and began wondering if there is a general theorem that a number of a given form is the sum of two squares. I ...
3
votes
4answers
140 views

what are linear divisors of integer powers?

I have been trying to prove that $n^4$ is eithere divisible by $5k$ or $5k+1$, couldn't help wonder if there is a more general theme to try later , namely if it is true that $n^m$ is divisble by at ...