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

learn more… | top users | synonyms

1
vote
2answers
124 views

Solving the equation $ax + c \equiv b \mod {n}$

Alright, I can go through and solve equations that do not have the "$+ c$" involved, i.e.: $ax \equiv b \mod{n}$. However, I do not know what to do when a "$+ c$" is incorporated. How does that $c$ ...
0
votes
2answers
82 views

Spanning Difference Sets of near optimal size

Let $n$ be an integer ($n>1$). Show that there exists a proper subset $A$ of $\{1,2,\cdots, n\}$ such that the following holds: the numbers of elements of $A$ is no more than $2[\sqrt n]$+1. ([x] ...
2
votes
2answers
249 views

A “fast” approach to solve $2^{133} \equiv x \mod 133 $

I have to solve this equation $2^{133} \equiv x \mod 133 $.Using Euler's theorem I reduced it to $2^{25} \equiv x \mod 133$ but I couldn't think off any fast way to proceed after this. Any ideas?
2
votes
1answer
54 views

Distributivity of a dot product-like operation

Let $b_1, \ldots, b_n \in \mathbb{N}$. For $x, y \in \mathbb{Z}^n$, define $x \cdot y$ as $\newcommand{\lcm}{\operatorname{lcm}}$ $$x \cdot y = \left(\sum_{i=1}^n (x_i \text{ mod } b_i)(y_i ...
2
votes
4answers
157 views

Distributivity mod an integer

Let $a,b,c,m \in \mathbb{Z}$, is it always the case that $$a((b+c) \text{ mod } q) \text{ mod } q = (ab \text{ mod } q + ac \text{ mod } q) \text{ mod } q$$
5
votes
3answers
415 views

Powers as a complete residue system modulo $p$?

Question 1. With $0 < a < p$, $p$ prime and $\gcd(a,p-1)=1$, is it true that $0, 1, 2^a, ...,(p-1)^a$ is a complete residue system modulo $p$? If not, will a similar statement hold? Question ...
5
votes
3answers
324 views

Properties of Fermat primes

Fermat primes 17 and 257 appear a lot in the prime composition of numbers of the form $a^{2^n}+1$. For example, $11^8+1$ is divisible by 17 and $11^{32}+1$ is divisible by 257. I have verified the ...
5
votes
1answer
968 views

Probability that two random numbers are coprime

This is a really natural question for which I know a stunning solution. So I admit I have a solution, however I would like to see if anybody will come up with something different. The question is ...
2
votes
1answer
301 views

Properties of the greatest common divisor and least common multiple

Let $a$, $b$, $c \in \mathbb{N}$. $[a, b]$ denotes $\mathrm{lcm}(a, b)$ and $(a,b)$ denotes $\gcd(a, b)$ Show that $(a,[b,c]) = [(a,b),(a,c)]$. $[a,(b,c)] = ([a,b],[a,c])$.
2
votes
4answers
889 views

Show that every prime $p>3$ is either of the form $6n+1$ or of the form $6n+5$

Show that every prime $p>3$ is either of the form $6n+1$ or of the form $6n+5$, where $n=0,1,2, \dots$
1
vote
0answers
280 views

How do I calculate cost savings and profits in this example?

How are profits and cost savings calculated in this table? Is there enough given data to calculate these two? Here is what I ...
4
votes
4answers
862 views

Modular Arithmetic question, possibly involving Chinese remainder theorem

'6 professors begin courses of lectures on Monday, Tuesday, Wednesday, Thursday, Friday and Saturday, and announce their intentions of lecturing at intervals of 2,3,4,1,6,5 days respectively. The ...
2
votes
1answer
629 views

Even numbers greater than 6 as sum of two specific primes

It is well known fact that it is very hard to prove Goldbach's strong conjecture but perhaps some weaker variations can be proved ,so my question is: Is it true that every even number greater than 6 ...
1
vote
2answers
279 views

Modular Fibonacci series

My second observation is the following. Let $p$ be a prime not equal to $5$. Then $5$ is a quadratic residue modulo $p$ if and only if $p\equiv\pm1\pmod5$. And $5$ is not a quadratic residue modulo ...
2
votes
5answers
797 views

Zeros of the decimal representation of $k!$

I'd like a hint for the question: For how many positive integers $k$ does the ordinary decimal representation of the integer $k!$ end in exactly $99$ zeros? Thanks.
3
votes
2answers
406 views

A conjecture about the form of some prime numbers

Let $k$ be an odd number of the form $k=2p+1$ ,where $p$ denote any prime number, then it is true that for each number $k$ at least one of $6k-1$, $6k+1$ gives a prime number. Can someone prove or ...
-4
votes
1answer
120 views

How to prove that $p^k|ab$ if and only if $p^k|a$ and $p^k|b$?

Let p be prime, $k \in$ N and let $a,b \in$ Z such that gcd(a,b)=1. How to prove that $p^k|ab$ if and only if $p^k|a$ and $p^k|b$? Trying: (<=) $p^k |a$ and $p^k|b$. Then $a=p^kq$ and $ ...
2
votes
6answers
196 views

Prove that for all $n\in\mathbb{N}, (n−1)^3+ n^3 \neq (n+1)^3$

Prove that for all $n\in\mathbb{N}, (n−1)^3+ n^3 \neq (n+1)^3$ Can someone give me a hint? I can only use properties of natural numbers... don't know how to write up a formal and correct proof ...
2
votes
1answer
105 views

Is it possible to know if sums of powers of a number is divisible by another number?

Is there a way to find whether a number (say $A$) formed by summing powers of another number (say $B$) is divisible by another number $C$? $A$ is a number like, for example, $B^1+B^3$. We can use a ...
4
votes
2answers
223 views

Integer solutions to $(a_1+a_2+\cdots+a_n)^n=a_1a_2\cdots a_n$?

Are there any positive nonzero integer solutions to $(a_1+a_2+\cdots+a_n)^n=a_1a_2\cdots a_n$ for $n>1$? If it helps, there are no solutions for $n=2$ because, otherwise, if $a_1$ and $a_2$ were ...
1
vote
4answers
697 views

How to use fundamental theorem of arithmetic to conclude that $\gcd(a^k,b^n)=1$ for all $k, n \in$ N whenever $a,b \in$ N with $\gcd(a,b)=1$?

How to use fundamental theorem of arithmetic to conclude that $\gcd(a^k,b^n)=1$ for all $k, n \in$ N whenever $a,b \in$ N with $\gcd(a,b)=1$? Fundamental theorem of arithmetic: Each number $n\geq 2$ ...
-1
votes
1answer
116 views

How to conclude that $a=2$ and $n$ is prime [closed]

Suppose that $a^n-1$ is prime for some $a>1$ and $n>1$. How to conclude that $a=2$ and $n$ is prime. [Hint! We have $a^{kl}-1 = (a^k-1)(a^{k(l-1)}+a^{k(l-2)}+ \cdots +a^k+1)$ whenever $n=kl$ ...
2
votes
1answer
155 views

Help proving two conjectures about prime factorization and the floor function

Let me first pose the questions free of context: Given prime $p$ and positive integers $b$ and $N$, define $$F(p,b,N) = \Big\lfloor (1/b) \sum_{i=1}^\infty \lfloor N/p^i \rfloor \Big\rfloor.$$ ...
6
votes
4answers
189 views

For any natural $n$, how could we prove that $\sum\limits_{i=1} ^n (i^2+3i+1) i!= (n+3)(n+1)! - 3$

How could we prove this ? $$\sum_{i=1} ^n (i^2+3i+1)\times i!= (n+3) \times (n+1)!-3$$ I did with induction, what I want to know is about other ways to prove this.
3
votes
2answers
335 views

Every decreasing sequence of natural numbers terminates

How do we prove that every decreasing sequence of natural numbers terminates using the well ordering principle?
2
votes
5answers
463 views

Prove: there exist infinitely many integers $k$ such that $k$ is not divisible by 5 and $12k+5$ is composite

Prove that there exist infinitely many integers $k$ such that $k$ is not divisible by 5 and $12k+5$ is composite
3
votes
1answer
664 views

How to find $\gcd(f_{n+1}, f_{n+2})$ by using Euclidean algorithm for the Fibonacci numbers whenever $n>1$?

Find $\gcd(f_{n+1}, f_{n+2})$ by using Euclidean algorithm for the Fibonacci numbers whenever $n>1$. How many division algorithms are needed? (Recall that the Fibonacci sequence $(f_n)$ is defined ...
4
votes
1answer
222 views

Expressing any given number in the form of $x^y + y^x$

I was told by one of my friends that any given positive integer can be expressed in the form of $x^y + y^x$ where x & y are integers. For example: 17 = $2^3+3^2$ Surprisingly,this could be done ...
10
votes
5answers
248 views

Is there a single or best reason that 2 is an exceptional prime?

I've recently been studying some elementary number theory, and I've frequently come across the fact that there are a fair number of results (the main one being the law of quadratic reciprocity) for ...
3
votes
6answers
312 views

Would like a proofreading of my proof

Prove that if $n\in\mathbb Z$, then $n^2$ is of the form $3q$ or $3q+1$ for some $q\in\mathbb Z$ I would like to show that 3q+2 is = 3q+1 thus $n^2$ can be of the form of 3q or 3q+1. Case one ...
0
votes
1answer
100 views

Can this be proved?

Let n,k be such positive integers that $n\geq5$ and $k\geq2$ . How to prove next conjecture: $\forall n$ $\exists k$ ,such that n=3k-1 $\vee$ n=3k $\vee$ n=3k+1 .It is easy to see that for k=2 we get ...
0
votes
3answers
739 views

Analytical Reasoning Question II

I have yet another analytical question that got me A five-digit number is formed using digits 1, 3, 5, 7 and 9 without repeating any one of them. What is the sum of all such possible numbers? ...
2
votes
1answer
103 views

If $f:\mathbb{Z}\to\mathbb{Z}$ has period $q$ modulo for any $q$, is it necessarily a polynomial?

If $f:\mathbb{Z}\to\mathbb{Z}$ satisfies the property $f(a+q)\equiv f(a)\pmod{q}$ for all $a\in\mathbb{Z},q\in\mathbb{N}$, can we conclude that $f(n)$ is a polynomial function? Seems like it should be ...
2
votes
3answers
172 views

show that $\gcd(a_1, \dots, a_n) = \gcd(a_1, \dots, a_{n-2},\gcd(a_{n-1},a_n))$

Let $a_1, \dots, a_n \in \mathbb Z$ such that $a_{i_0} \neq 0$ for some $i_0 \in \{1, \dots, n\}$. How to show that $\gcd(a_1, \dots, a_n) = \gcd(a_1, \dots, a_{n-2},\gcd(a_{n-1},a_n))$. (Hint: show ...
9
votes
6answers
627 views

Proof of the equality $\sum\limits_{k=1}^{\infty} \frac{k^2}{2^k} = 6$

Show that for $k$ running over positive integers $$ \sum_{k=1}^\infty \frac{k^2}{2^k}=6 .$$ We can use finite calculus.
1
vote
1answer
266 views

A “fast” way to compute number of pairs of positive integers $(a,b)$ with lcm $N$

I am looking for a fast/efficient method to compute the number of pairs of $(a,b)$ so that its LCM is a given integer, say $N$. For the problem I have in hand, $N=2^2 \times 503$ but I am very ...
3
votes
2answers
162 views

Given $a_2 = 2$ and $a_{mn}=a_m a_n$ for $m$, $n$ coprime, show $a_n=n$ for all natural numbers

I'm a bit stuck on this... my only thought was to use second induction on $n$, which works well enough for the case where $n$ is composite and has two or more distinct prime factors, but if $n$ is ...
0
votes
4answers
187 views

Help with easy proof

My name is Dennis and I need help solving. Show that if $n\in\mathbb Z$ is odd, then $n$ is of the form $4q+1$ or $4q+3$ for some $q\in\mathbb Z$. Now I know this is true so can't use a proof by ...
0
votes
1answer
351 views

How can i prove that every terminating real number is rational and every repeating real number is a rational number. [duplicate]

Possible Duplicate: How can I prove that all rational numbers are either terminally real or repeating real numbers? How can i prove that every terminating real number is rational and every ...
4
votes
1answer
64 views

Value of $k$ satisfying this condition

In a pile you have 100 stones. A partition of the pile in $k$ piles is good if: 1) the small piles have different numbers of stones; 2) for any partition of one of the small piles in 2 smaller ...
7
votes
5answers
431 views

Proof that $6^n$ always has a last digit of $6$

Without being proficient in math at all, I have figured out, by looking at series of numbers, that $6$ in the $n$-th power always seems to end with the digit $6$. Anyone here willing to link me to a ...
-2
votes
3answers
839 views

How to show that $\gcd(ab,n)=1$?

Let $\gcd(a,n)=\gcd(b,n)=1$. How to show that $\gcd(ab,n)=1$? This is a problem that is an exercise in my course.
0
votes
3answers
224 views

Let a|c and b|c such that gcd(a,b)=1, Show that ab|c

Let a|c and b|c such that greatest common divisor (gcd) gcd(a,b)=1, Show that ab|c.
1
vote
1answer
678 views

Determining number of positive integer solutions to Ax + By + Cz + Dw < Z ?

I would like a method to determine the number of positive integer solutions for an linear inequality, of the form: $Ax + By + ... < Z$ given integer A,B, .. Z and integer $x,y,z,w \ge ...
-2
votes
3answers
1k views

How to show that $\gcd(a,b) = ax+by \implies \gcd(x,y)=1$? [closed]

Assume that $$ \gcd(a,b)=ax+by $$ for some $a, b, x, y \in \mathbb Z$. How do I show that $\gcd(x,y)=1$? (Hint: contradiction.)
2
votes
4answers
2k views

How can I prove that all rational numbers are either terminally real or repeating real numbers?

I am trying to figure out how to prove that all rational numbers are either terminally real or repeating real numbers, but I am having a great difficulty in doing so. Any help will be greatly ...
34
votes
7answers
3k views

Project Euler, Problem #25

Problem #25 from Project Euler asks: What is the first term in the Fibonacci sequence to contain 1000 digits? The brute force way of solving this is by simply telling the computer to generate ...
15
votes
3answers
623 views

Finding when $(a-n)(b-n)|(ab-n)$

Given $n$ and $k$, find the number of pairs of integers $(a, b)$ which satisfy the conditions $n < a < k, n < b < k$ and $(ab-n)$ is divisible by $(a-n)(b-n)$. Given: $0 ≤ n ≤ 100000, \ n ...
3
votes
1answer
64 views

Collection of congruencies

I have been going around various questions based on number theory in this forum, and what I have found is that congruencies serve as an important tool in many of the questions and actually simplify ...
1
vote
1answer
209 views

Prove equivalence of Diffie-Hellman shared secret

How can I prove that: $ (g^b \bmod{p})^a \bmod{p} = (g^a \bmod{p})^b \bmod{p}$ where p is a prime number, g is a primitive root of p, and a and b are integers. While I understand that $(g^b)^a = ...